[백준 3687][C++] 성냥개비 (Gold 2)

[문제보기]

 3687. 성냥개비

3687번: 성냥개비

 

[풀이과정]

이 문제는 최대값을 구하는 부분은 쉬웠지만, 최소값을 구하는 부분이 어려웠다.

 

1. 최소값 구하기

Min_Dp[]를 통해 최소값에 대한 배열을 만들었다. 

손으로 10개까지의 정답을 구해보면 9개부터는 두자리 숫자가 만들어지는 것을 볼 수 있다.

그리고 문제에서 숫자의 처음에는 0이 나올 수 없다고 했기 때문에 6개로 만들 수 있는 최소수는 6이 된다.

(그 이후로는 0 가능) 

for문을 통해 2~8까지의 숫자를 num[]배열을 통해 Min_Dp[]에 넣어주었다. 

 

그 이후의 숫자는 점화식을 통해 Min_Dp[]를 채워주었는데, 

i ) n = 9인 경우

   min(Min_Dp[9] vs Min_Dp[9 - 2] * 10 + num[2])

   min(Min_Dp[9] vs Min_Dp[9 - 3] * 10 + num[3])

   min(Min_Dp[9] vs Min_Dp[9 - 4] * 10 + num[4])

   min(Min_Dp[9] vs Min_Dp[9 - 5] * 10 + num[5])

   min(Min_Dp[9] vs Min_Dp[9 - 6] * 10 + num[6])

   min(Min_Dp[9] vs Min_Dp[9 - 7] * 10 + num[7])

   min(Min_Dp[9] vs Min_Dp[9 - 8] * 10 + num[8])

형태가 만들어진다. 이는 성냥개비를 나눠서 최소수를 만들어야되기 때문에 이런 식이 만들어지고,

8까지하는 이유는 위에서 2~8까지의 정확한 답을 알기 때문에 8까지 확인을 한다.

결국 점화식은 

for(int i=9; i<101; i++){

     Min_Dp[i] = Min_Dp[i-2]*10 + num[2];

     for(int j=3; j<8; j++){

          Min_Dp[i] = min(Min_Dp[i], Min_Dp[i-j]*10 + num[j]);

     }

}

이 된다.

 

 

2. 최대값 구하기

성냥 개비를 가지고 만들수 있는 값중에 2개로는 1, 3개로는 7이 가장 큰 값을 차지한다

4는 11 (4 = 2+2  따라서, 1 + 1 = 11), 

5는 71 (5 = 3+2  따라서, 7 + 1 = 71)

이렇게 짝수는 11111.....

홀수는 711111.... 형태가 최대값을 만든다.

 

[소스코드]

#include <iostream>

using namespace std;

int T, n;
int num[9] = {0, 0, 1, 7, 4, 2, 0, 8, 10};
long long Min_Dp[101];

void Min_Calculate(){
    for(int i=1; i<9; i++){
        Min_Dp[i] = num[i];
    }
    Min_Dp[6] = 6;

    for(int i=9; i<101; i++){
        Min_Dp[i] = Min_Dp[i-2]*10 + num[2];

        for(int j=3; j<8; j++){
            Min_Dp[i] = min(Min_Dp[i], Min_Dp[i-j]*10 + num[j]);
        }
    }
}

int main(){
    
    Min_Calculate();
    cin >> T;
    
    while(T--){
        cin >> n;
        
        cout << Min_Dp[n] << " ";

        string Max = "";
        while(n){
            if(n % 2 != 0){
                cout << 7;
                n -= 3;
            }
            else{
                cout << 1;
                n -= 2;
            }
        }

        cout << "\n";
    }
}

 

[해결 과정 중 실수한 부분]

처음에는 자리수가 많아질것을 예상하고 string값을 통해 값을 저장해주었다. 하지만 백준 사이트의 다른분들의 코드를 보고 long long으로 정답을 만들 수 있는 것을 보고 코드를 고쳤고, 더 깔끔해졌다.