[백준 3687번] 성냥개비

문제 링크: 3687번 제목

https://www.acmicpc.net/problem/3687

 

1. 최댓값 만들기

어려운 부분이 없다. 최댓값을 만들고자 한다면 먼저 ①자리수 ②앞자리를 고려해야 한다. 즉 자리수를 무작정 늘린 후 앞자리를 가장 크게 하면 된다.

이를 위해 성냥을 가장 적게 필요로 하는 1을 최대한 만든다. n이 홀수일 때는 3개를 이용해 7을 하나 만들고 맨 앞에 배치하여, 남는 성냥이 없도록 한다.

 

2. 최솟값 만들기

숫자를 쭉 나열하다보면 뭔가 규칙이 보인다.

성냥의 개수	최솟값(독립적)	최솟값(의존적)
2	1	1
3	7	7
4	4	4
5	2	2
6	6	0
7	8	8
8	10	01
9	18	07
10	22	04
11	20	02
12	28	00
13	68	08
14	88	88
15	108	007
...
22		0004

 

최솟값(독립적)은, 문제에서 요구하는 값이다. 반면 최솟값(의존적)은, 첫 자리에 0이 올 수 없다는 제약을 모두 무시하고, 해당 성냥 개수를 통해 만들 수 있는 가장 작은 수를 뜻한다.

 

일단, 우리는 성냥 개수를 통해 최솟값(독립적, 의존적)의 자리수를 알 수 있다. 7의 배수마다 구분되는데, 이는 숫자 중 가장 많은 성냥을 필요로 하는 숫자가 7이기 때문이다. 성냥 개수가 15개일 때에는, 자리수를 적게 하고자 노력해서 7을 2개 만들더라도 성냥 1개가 남는다는 것을 생각해보면 된다.

 

성냥 개수가 15개일 때를 계속해서 살펴보자. 일단 가장 작은 숫자를 만들고자 첫 자리에 1을 넣어본다. 이미 최소 자리수가 3인 것을 알고 있으므로, 1을 만드는 데에 필요한 성냥 2개를 제외하고 남은 13개로 만들 수 있는 최솟값을 찾는다. 현재 코드는 bottom-up 방식이므로, 성냥 13개로 만들 수 있는 최솟값은 이미 구해진 상태이다. 그리고 이 때에는 최솟값(의존적)을 사용해야 하는데, 이미 가장 큰 자리수를 가장 작게 하기 위해 최선을 다했고, 그리고 지금 우리가 찾은 것은 두 번째 자리 이후의 숫자들이기 때문에 최솟값의 맨 앞 자리가 0이 되어도 상관없기 때문이다. 이러한 점을 참고해서, 1 뒤에 n=13일 때의 최솟값(의존적) 08을 붙인다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] cost = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();

        // create dp
        String dp[] = new String[101];
        dp[2] = "1"; dp[3] = "7"; dp[4] = "4"; dp[5] = "2"; dp[6] = "0"; dp[7] = "8";
        for (int i = 8; i <= 100; i++) {
            StringBuilder r = new StringBuilder();
            int level = i / 7; if (i % 7 == 0) level--;
            if (7*(level-1)+1 <= i-6 && i-6 <= 7*level) {
                r.append(0).append(dp[i-6]);
            } else {
                r.append(8).append(dp[i-7]);
            }
            dp[i] = r.toString();
        }

        // create v
        String v[] = new String[101];
        v[2] = "1"; v[3] = "7"; v[4] = "4"; v[5] = "2"; v[6] = "6"; v[7] = "8";
        for (int i = 8; i <= 100; i++) {
            int copy = i;

            int numDigit = i / 7 + 1; if (i % 7 == 0) numDigit--;
            int[] r = new int[numDigit];
            for (int j = 1; j <= 9; j++) {
                r[0] = j;
                if (7*(numDigit-2)+1 <= i-cost[j] && i-cost[j] <= 7*(numDigit-1)) {
                    for (int k = 0; k < dp[i-cost[j]].length(); k++) {
                        r[1+k] = dp[i-cost[j]].charAt(k) - '0';
                    }
                    break;
                }
            }

            StringBuilder t = new StringBuilder();
            for (int j = 0; j < r.length; j++) t.append(r[j]);
            v[copy] = t.toString();
        }

        while (test-- > 0) {
            int n = Integer.parseInt(br.readLine());
            answer.append(v[n]).append(' ').append(getMax(n)).append('\n');
        }
        System.out.print(answer);
    }

    static StringBuilder getMax(int n) {
        StringBuilder res = new StringBuilder();
        if (n % 2 == 0) {
            for (int i = 0; i < n/2; i++) res.append('1');
        } else {
            res.append('7');
            for (int i = 0; i < (n-3)/2; i++) res.append('1');
        }
        return res;
    }
}