[BaekJoon] 3687번 - 성냥개비 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 성냥개비로 만들 수 있는 가장 작은 수와 가장 큰 수를 찾아야하는 문제로 가장 작은 수는 다이나믹 프로그래밍으로, 가장 큰 수는 그리디 알고리즘으로 찾을 수 있다.

가장 작은 수의 경우 dp 테이블은 성냥개비 $x$ 개로 만들 수 있는 가장 작은 수를 저장하면 된다. $0$ 부터 $9$ 까지 각 숫자를 만드는데 필요한 성냥개비 수를 알 수 있으므로 이를 통해 dp 테이블을 초기화하면 아래와 같이 된다.

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

한 자리 수를 만드는데는 최소 2개에서 최대 7개까지 사용할 수 있다. 따라서 숫자 $i$ 를 만드는데 필요한 성냥개비의 수 $dp[i]$ 는 2부터 7까지의 $j$ 에 대해 $dp[i - j] + dp[j]$ 로 $j$ 개를 덜 쓰고 만든 숫자에 $j$ 개를 쓴 숫자를 붙여 새로운 수를 만들고 이 값과 기존의 $dp[i]$ 중 작은 값을 저장하면 된다. 이때 성냥개비 6개로는 "0"을 만드는게 더 작은 수가 되는 것을 분기처리 해주었다.

가장 큰 수는 그리디하게 찾을 수 있는데 자릿수를 최대한 늘리는 것이 유리하므로 성냥개비의 수가 짝수개면 전부 1로 만들면 되고, 성냥개비의 수가 홀수개면 맨 앞에 7, 나머지는 1로 만들면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static final int MAX = 100;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] dp = new String[1 + MAX];
        dp[2] = "1";
        dp[3] = "7";
        dp[4] = "4";
        dp[5] = "2";
        dp[6] = "6";
        dp[7] = "8";

        for (int i = 8; i <= MAX; i++) {
            for (int j = 2; j <= 7; j++) {
                if (dp[i - j] == null) continue;

                String tmp = dp[i - j];
                if (j != 6) {
                    tmp += dp[j];
                } else {
                    tmp += "0";
                }

                if (dp[i] == null) {
                    dp[i] = tmp;
                } else {
                    dp[i] = min(dp[i], tmp);
                }
            }
        }

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append(" ").append(findMax(n)).append("\n");
        }

        System.out.println(sb);
    }

    static String min(String a, String b) {
        if (a.length() != b.length()) return a.length() > b.length() ? b : a;
        return a.compareTo(b) > 0 ? b : a;
    }

    static String findMax(int n) {
        if (n % 2 == 0) return "1".repeat(n / 2);
        return "7" + "1".repeat((n - 3) / 2);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100;
string dp[1 + MAX] = {"", "", "1", "7", "4", "2", "6", "8"};

string findMin(string& a, string& b) {
    if (a.size() != b.size()) return a.size() > b.size() ? b : a;
    return a > b ? b : a;
}

string findMax(int n) {
    if (n % 2) return "7" + string((n - 3) / 2, '1');
    return string(n / 2, '1');
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 8; i <= MAX; i++) {
        for (int j = 2; j <= 7; j++) {
            if (dp[i - j].empty()) continue;

            string tmp = dp[i - j];
            if (j != 6) {
                tmp += dp[j];
            } else {
                tmp += "0";
            }

            if (dp[i].empty()) {
                dp[i] = tmp;
            } else {
                dp[i] = findMin(dp[i], tmp);
            }
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        cout << dp[n] << ' ' << findMax(n) << '\n';
    }
}

---