[ BOJ ][JAVA][3687] 성냥개비

www.acmicpc.net/problem/3687

3687번: 성냥개비

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1877	650	473	37.098%

문제

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

출력

각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.

예제 입력 1

4
3
6
7
15

예제 출력 1

7 7
6 111
8 711
108 7111111

코드

import java.io.*;
import java.util.*;

public class p3687 {
    static int tc, n;
    static long[] minDp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        /*
            i : 성냥개비의 개수, dp[i] : 만들 수 있는 가장 작은 숫자
            dp[0] = 0;
            dp[1] = 0;
            dp[2] = 1; (dp[2])
            dp[3] = 7; (dp[3])
            dp[4] = 4; (dp[4])
            dp[5] = 2; (dp[5])
            dp[6] = 0; (dp[6])
            dp[7] = 8; (dp[7])
            **
            dp[8] = 10; (dp[2] + dp[6])
            dp[9] = 18; (dp[2] + dp[7])
            dp[10] = 22; (dp[5] + dp[5])
            dp[11] = 20; (dp[5] + dp[6])
            dp[12] = 28; (dp[5] + dp[7])
            dp[13] = 68; (dp[6] + dp[7])
            dp[14] = 88; (dp[7] + dp[7])
            **
            dp[15] = 108; (dp[2] + dp[6] + dp[7])
            ...
        */
        while(tc-- > 0) {
            n = Integer.parseInt(br.readLine());
            // 최소
            minDp = new long[101];
            Arrays.fill(minDp, Long.MAX_VALUE);
            minDp[2] = 1;
            minDp[3] = 7;
            minDp[4] = 4;
            minDp[5] = 2;
            minDp[6] = 6;
            minDp[7] = 8;

            minDp[8] = 10;

            int[] arr = {1, 7, 4, 2, 0, 8};
            for (int i = 9; i <= 100; i++) {
                for (int j = 2; j <=7; j++) {
                    String line = ""+ minDp[i - j] + arr[j - 2];
                    minDp[i] = Math.min(minDp[i], Long.parseLong(line));
                }
            }

            /// 최대
            StringBuilder max = new StringBuilder();
            long a = n / 2;
            long b = n % 2;

            if (b == 1) {
                max.append("7");
            } else {
                max.append("1");
            }

            for (int i = 1; i < a; i++) {
                max.append("1");
            }

            System.out.println(minDp[n]+" "+max.toString());
        }
    }
}