[Java] 백준 3687. 성냥개비

📌 문제 링크 - https://www.acmicpc.net/problem/3687

 

 

---

 

 

 

 

 

 

문제

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

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

 

 

입력

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

 

 

 

출력

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

 

 

 

 

 

 

---

 

 

풀이

가장 큰 수와 가장 작은 수를 만드는 방법을 나누어 생각해보자.

 

가장 큰 수 (그리디)

가장 큰 수를 만들기 위해서는 자릿수를 최대한 늘려야 한다. 1은 2개의 성냥으로 만들 수 있으므로 가장 많이 사용할 수 있다.

예를 들어 성냥 6개로 9를 만들 수 있지만, 1은 2개의 성냥이 필요하므로 111을 만들 수 있다. 

 

 

따라서 n 개의 성냥으로 만들 수 있는 가장 큰 수는 짝수일 경우 전부 1로 자릿수를 최대한 늘려주고, 홀수일 경우 성냥 3개로 만들 수 있는 7을 앞자리에 놓고 나머지 수를 1로 채워주면 된다.

 

성냥 6개 (짝) -> 111   (2개 + 2개 + 2개)

성냥 9개 (홀) -> 7 + 111 = 7111   (3개 + 6개)

 

 

가장 작은 수 (DP)

가장 작은 수를 구할 땐 자릿수보다 숫자의 값이 작아야 하므로 다양한 숫자를 조합해야 한다.

dp[n] = n 개의 성냥으로 만들 수 있는 가장 작은 수

min[n] = n 개의 성냥으로 만들 수 있는 가장 작은 한 자릿수

 

성냥 2개 : 1

성냥 3개 : 7

성냥 4개 : 4

성냥 5개 : 2

성냥 6개 : 0  (0으로 시작할 수 없기 때문에 dp는 6으로 초기화해준다.)

성냥 7개 : 8

 

for(int i=8; i<MAX_N; i++) {
    for(int j=2; j<8; j++) {
        dp[i] = Math.min(dp[i], dp[i-j] * 10 + min[j]);
    }
}

한 자릿수 숫자를 만들기 위해 필요한 성냥의 최대 개수는 7개다. 

따라서 성냥이 8개 이상일 경우는 두 자리 이상의 수를 만들 수 있게 되므로 8개부터는 여러 숫자를 조합하여 만들 수 있는 가장 작은 수를 구해줘야 한다. 

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/3687
public class Main_3687 {
    private static final long INF = Long.MAX_VALUE;
    private static final int MAX_N = 101; // (2 ≤ n ≤ 100)
    private static final int[] min = {0, 0, 1, 7, 4, 2, 0, 8}; // i개로 만들 수 있는 작은 수
    private static long[] dp; // i개의 성냥으로 만들 수 있는 최솟값


    public static void main(String[] args) throws IOException {
        init();
        sol();
    }//main


    private static void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder ans = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

        int n;
        String max;

        while(T-- > 0) {
            n = Integer.parseInt(br.readLine()); // 성냥개비의 개수
            max = getMax(n);

            ans.append(dp[n]).append(' ');
            ans.append(max).append('\n');
        }

        System.out.print(ans);
        br.close();
    }//sol


    private static String getMax(int n) {
        StringBuilder max = new StringBuilder();
        int start = (n % 2 == 0) ? 2 : 3; // 1은 성냥 2개, 7은 성냥 3개
        long num = n - start;

        max.append(min[start]);
        // 나머지는 1로 채우기
        for(int i=0; i<num; i+=2) {
            max.append(1);
        }

        return String.valueOf(max);
    }//getMax


    private static void init() {
        dp = new long[MAX_N]; // n개의 성냥으로 만들 수 있는 최솟값
        Arrays.fill(dp, INF);

        for(int i=2; i<8; i++) {
            dp[i] = min[i];
        }
        dp[1] = 9; // 1개는 불가능하므로 가장 큰 9
        dp[6] = 6; // 0으로 시작할 수 없으므로 0 다음으로 작은 6

        for(int i=8; i<MAX_N; i++) {
            for(int j=2; j<8; j++) {
                dp[i] = Math.min(dp[i], dp[i-j] * 10 + min[j]);
            }
        }

    }//init


}//class