백준 3687번 - 성냥개비

문제

백준 3687번 - 성냥개비

---

아이디어

가장 작은 수는 DP로 구하고, 가장 큰 수는 그리디 관점에서 구한다.

1. dp 배열 초기화

String[] dp = new String[101];
Arrays.fill(dp, String.valueOf(Long.MAX_VALUE));

dp[2] = "1";
dp[3] = "7";
dp[4] = "4";
dp[5] = "2";
dp[6] = "6";
dp[7] = "8";

• dp[i]는 성냥개비가 i개일 때 가장 작은 수이다.
• 성냥개비가 2~7개일 때는 한자리 수를 만들면 된다. 수는 0으로 시작하면 안되기 때문에 6개는 6이어야 한다.

2. dp 배열 채우기

String[] arr = {"", "", "1", "7", "4", "2", "0", "8"};

for (int i = 8; i <= 100; i++) {    //성냥개비 개수
    for (int j = 2; j <= 7; j++) {  //숫자를 표현하는 데 성냥개비 최소 2개 ~ 최대 7개 필요
    
        String original = dp[i];
        String newNum = dp[i - j] + arr[j];
        
        //자릿수가 애초에 작은 경우
        if (original.length() < newNum.length()) continue;
        
        //자릿수가 적거나, 자릿수는 같고 비교했을 때 더 큰 경우
        if (original.length() > newNum.length() || original.compareTo(newNum) > 0) {
            dp[i] = newNum;
        }
    }
}

• 성냥개비 8개부터는 최소 두자리수가 된다. 반복문으로 성냥개비 i개 되는 다양한 조합을 살펴본다.
• 첫번째 자리 외에는 숫자 0이 가능하기 때문에 성냥개비 6개로 0을 만들어야 한다. (arr[6] = "0")

3. 테스트 케이스 반복 후 결과 출력

int tc = Integer.parseInt(br.readLine());

while (tc-- > 0) {

    int n = Integer.parseInt(br.readLine());
    
    String min = dp[n];
    String max = (n % 2 == 0)
            ? "1".repeat(n / 2)
            : "7" + "1".repeat((n - 3) / 2);
            
    sb.append(min).append(" ").append(max).append("\n");
}

System.out.print(sb);

• 가장 작은 수는 위에서 구했던 dp 배열에서 구한다.
• 가장 큰 수는 간단한 계산식으로 구할 수 있다.
• 가장 큰 수가 되기 위해서는 무조건 자리수가 많은 것이 유리하다. 자릿수가 많아지려면 최소의 성냥개비로 가능한 숫자를 이어붙여야 한다. 숫자 1이 성냥개비 2개로 최소 성냥개비 개수이다.
• 즉, 성냥개비 개수가 짝수면 1을 만드는데 모두 소진해서 최대한 자리수를 많게 만든다.
• 성냥개비 개수가 홀수일 때도 원리는 같다. 하지만, 성냥개비가 하나 남는다. 마침 숫자 7이 성냥개비 3개를 사용하기 때문에 남은 3개로는 숫자 7을 만드는 데 사용할 수 있다.
• 즉, 가장 큰 수는 1 또는 1, 7로만 이루어진다.
• 가장 큰 수도 어떻게 DP로 가능하겠지만 규칙과 원리를 찾아서 한번의 계산식으로 구할 수 있다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

---

코드 구현 - 자바

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

public class BJ_3687 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] dp = new String[101];

        Arrays.fill(dp, String.valueOf(Long.MAX_VALUE));

        dp[2] = "1";
        dp[3] = "7";
        dp[4] = "4";
        dp[5] = "2";
        dp[6] = "6";
        dp[7] = "8";

        String[] arr = {"", "", "1", "7", "4", "2", "0", "8"};

        for (int i = 8; i <= 100; i++) {    //성냥개비 개수
            for (int j = 2; j <= 7; j++) {  //숫자를 표현하는 데 성냥개비 최소 2개 ~ 최대 7개 필요

                String original = dp[i];
                String newNum = dp[i - j] + arr[j];

                //자릿수가 애초에 작은 경우
                if (original.length() < newNum.length()) continue;

                //자릿수가 적거나, 자릿수는 같고 비교했을 때 더 큰 경우
                if (original.length() > newNum.length() || original.compareTo(newNum) > 0) {
                    dp[i] = newNum;
                }
            }
        }

        int tc = Integer.parseInt(br.readLine());

        while (tc-- > 0) {

            int n = Integer.parseInt(br.readLine());

            String min = dp[n];
            String max = (n % 2 == 0)
                    ? "1".repeat(n / 2)
                    : "7" + "1".repeat((n - 3) / 2);

            sb.append(min).append(" ").append(max).append("\n");
        }

        System.out.print(sb);
    }
}

코드 구현 - 파이썬

dp = [""] * 101
for i in range(101):
    dp[i] = str(10**18)

dp[2] = "1"
dp[3] = "7"
dp[4] = "4"
dp[5] = "2"
dp[6] = "6"
dp[7] = "8"
dp[8] = "10"

arr = ["", "", "1", "7", "4", "2", "0", "8"]

for i in range(2, 101):
    for j in range(2, 8):

        original = dp[i]
        new_num = dp[i - j] + arr[j]

        if len(original) < len(new_num):
            continue

        if len(original) > len(new_num) or original > new_num:
            dp[i] = new_num

t = int(input())

ans = []

for _ in range(t):
    n = int(input())

    min_val = dp[n]
    max_val = "1" * (n // 2) if n % 2 == 0 else "7" + "1" * ((n - 3) // 2)

    ans.append(f"{min_val} {max_val}")

print("\n".join(ans))