백준 3687 성냥개비 (Java)

1. 문제

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

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

입력

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

출력

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

 

2. 풀이

성냥의 개수가 주어졌을 때 만들 수 있는 최솟값과 최댓값을 따로 구해주어야 한다.

2-1. 최솟값

사실상 이 문제의 핵심이다. 우선 가지고 있는 성냥으로 나타낼 수 있는 최솟값을 dp 배열로 선언해준다.

            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;

dp[8] 부터는 1의 자리에 0이 들어갈 수 있기 때문에 여기까지 선언해준다.

            int[] count = {1, 7, 4, 2, 0, 8};

            for (int i = 9; i <= 100; i++) {
                for (int j = 2; j <= 7; j++) {
                    minDp[i] = Math.min(minDp[i - j] * 10 + count[j - 2], minDp[i]);
                }
            }

이 이후로는 성냥이 늘어날 때 마다 이 이전의 숫자에 count 만큼의 성냥으로 숫자를 만들어서 끼워넣어야 한다. 예를 들어보자

• 9개로 성냥을 만드는 경우는 2개의 성냥에 7개로 만들 수 있는 최솟값을 구해 붙이는 경우(18), 3개의 성냥에 6개로 만들 수 있는 최솟값을 구해 붙이는 경우(70)..., 7개로 만든 숫자에 2개로 최솟값을 만들어 붙이는 경우(81) 중 최솟값을 구해주면 된다. 

2-2. 최댓값

            //max 구하기
            StringBuilder maxBuilder = new StringBuilder();

            if (n % 2 == 0) {
                for (int i = 0; i < n / 2; i++) {
                    maxBuilder.append(1);
                }
            } else {
                maxBuilder.append(7);
                for (int i = 0; i < n / 2 - 1; i++) {
                    maxBuilder.append(1);
                }

            }

최댓값을 만들려면 우선 자릿수가 최대한 많아야 한다. 개수가 홀수일 경우 앞에 7을 붙이고 1로 자릿수를 채우는게, 짝수일 경우 모두 1로 채우는 것이 최댓값이 된다. 이는 long 배열을 넘어가므로 문자열로 만들어주어야 한다.

 

앞에서 만든 최솟값, 최댓값을 출력해주면 된다.

3. 코드 전문

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int t;
    static int n;


    //i를 만들기 위해 필요한 성냥의 수
    static long[] minDp;

    public static void main(String[] args) throws Exception{

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        t = Integer.parseInt(reader.readLine());

        for (int test = 0; test < t; test++) {

            n = Integer.parseInt(reader.readLine());


            //min 구하기

            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[] count = {1, 7, 4, 2, 0, 8};

            for (int i = 9; i <= 100; i++) {
                for (int j = 2; j <= 7; j++) {
                    minDp[i] = Math.min(minDp[i - j] * 10 + count[j - 2], minDp[i]);
                }
            }

            //max 구하기
            StringBuilder maxBuilder = new StringBuilder();

            if (n % 2 == 0) {
                for (int i = 0; i < n / 2; i++) {
                    maxBuilder.append(1);
                }
            } else {
                maxBuilder.append(7);
                for (int i = 0; i < n / 2 - 1; i++) {
                    maxBuilder.append(1);
                }

            }


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


        }



    }
}