[BOJ] 3687. 성냥개비

다이나믹 프로그래밍을 활용한 문제였다.

이 문제는 성냥개비를 활용하여 가장 큰 수와 가장 작은 수를 만들는 문제였다. 모든 조합의 경우를 확인하는 방법도 있지만 보다 효율적으로 확인할 수 있는 DP가 있기에 DP를 사용하여 큰 수, 작은 수를 각 각 구하였다.

우선 간단한 큰수의 경우 계속 자릿수를 늘려가는 방법 생각해보았다. 우선 가장 작은 성냥개비가 드는 수는 1로써 성냥 두개를 사용하게 되는데 이것을 이용하여 모든짝수를 구할 수 있었다. 홀수의 경우 7이 성냥 세개를 사용하는데 이것을 이용하여 하나의 홀수 + 나머지는 짝수를 사용하는 방식을 사용할 수 있었다. 따라서 다음과 같은 점화식을 사용할 수 있었다.
dp[2] = 1, dp[3] = 7, dp[i] = concat(dp[i-2], 1)
또한 이 문제에서는 최대 범위가 100까지인데 50자리의 숫자는 굉장히 크기 때문에 간단하게 스트링을 이용하여 문제를 풀었다.

작은 수의 경우는 일단 한자릿수의 성냥 개수를 가지고 만들 수 있는 작은 수들을 미리 확인한다음 두 자릿수의 성냥 개수 부터는 한자릿수의 성냥 개수를 하나씩 붙여가면서 만들 수 있는 수를 확인하여 가장 작은 수를 할당하는 방식을 사용하였다. 따라서 다음과 같은 점화식을 사용하였다.
dp[2]=1, dp[3]=7, dp[4]=4, dp[5]=2, dp[6]=6, dp[7]= 7, dp[8]=10, dp[i]= min(concat(dp[i-j], dp[j])) -> 2<=j<=7
여기서 주의할점은 j=6일때 dp[6]의 값을 사용하지 말고 0을 사용하는 것이다. 왜냐하면 6개의 성냥으로 0을 만들 수 있기 때문에 이것을 주의해야한다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_3687_성냥개비 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        String[] dpMax = new String[101];
 
        dpMax[2] = "1";
        dpMax[3] = "7";
        dpMax[4] = "11";
 
        for (int i = 5; i <= 100; i++) {
            dpMax[i] = dpMax[i - 2] + "1";
        }
 
        long[] dpMin = new long[101];
        for (int i = 2; i < 101; i++) {
            dpMin[i] = Long.MAX_VALUE;
        }
 
        dpMin[2] = 1;
        dpMin[3] = 7;
        dpMin[4] = 4;
        dpMin[5] = 2;
        dpMin[6] = 6;        //dp[6]은 원래 6 이것에 대한 처리 필요
        dpMin[7] = 8;
        dpMin[8] = 10;
 
        for (int i = 9; i <= 100; i++) {
            for (int j = 2; j <= 7; j++) {
                if (j == 6) {
                    dpMin[i] = Math.min(
                        dpMin[i],
                        Long.parseLong((dpMin[i - j] + "0"))
                    );
                } else {
                    dpMin[i] = Math.min(
                        dpMin[i],
                        Long.parseLong((dpMin[i - j] + "") + (dpMin[j] + ""))
                    );
                }
            }
        }
 
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            System.out.print(dpMin[num] + " ");
            System.out.println(dpMax[num]);
        }
    }
}