[백준] 3687번 : 성냥개비 Gold2(골드2) - JAVA[자바]

[Gold II] 성냥개비 - 3687

문제 링크

성능 요약

메모리: 13788 KB, 시간: 80 ms

분류

다이나믹 프로그래밍, 그리디 알고리즘

제출 일자

2024년 6월 7일 14:09:27

문제 설명

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

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

입력

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

출력

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

 

접근 방법

1. 문자열로 접근하여 숫자를 이어붙히는데 편리하게 사용한다.
2. dp[i] = dp[k] + dp[i - k] (k = 2 ~ (i- 2)까지) 점화식을 이용한다.
3. 7개까지는 직접 값을 넣어준 후 점화식을 이용해서 계산한다.

 

풀이 코드

import java.io.*;

/**
 * 문제: BOJ_3687_성냥개비
 * 메모리: 13788KB
 * 시간: 80ms
 * 접근 방법
 * 1. 문자열로 접근하여 숫자를 이어붙히는데 편리하게 사용한다.
 * 2. dp[i] = dp[k] + dp[i - k] (k = 2 ~ (i- 2)까지) 점화식을 이용한다.
 * 3. 7개까지는 직접 값을 넣어준 후 점화식을 이용해서 계산한다.
 */
public class Main {
    static String[] max, min;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        max = new String[101];
        min = new String[101];
        init();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int idx = Integer.parseInt(br.readLine());
            // 6이라면 최소값은 6으로 계산
            if(idx == 6){
                sb.append("6 ").append(getMax(idx));
            }else{
                sb.append(getMin(idx)).append(" ").append(getMax(idx));
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static String getMin(int idx) {
        if (min[idx] != null) {
            return min[idx];
        }

        for (int i = 2; i <= idx - 2; i++) {
            String front = min[i];

            // 6이 앞자리면 0이 아닌 6을 넣어준다.
            if(i == 6) front = "6";
            if (front == null) {
                getMin(i);
            }

            // null이면 새롭게 받아온다
            if (min[idx - i] == null) {
                getMin(idx - i);
            }

            String value = front + min[idx - i];
            if (min[idx] == null) {
                min[idx] = value;
            } else if (compare(min[idx], value).equals(min[idx])) {
                min[idx] = value;
            }
        }
        return min[idx];
    }

    private static String getMax(int idx) {
        if (max[idx] != null) {
            return max[idx];
        }

        max[idx] = "0";
        for (int i = 2; i <= idx - 2; i++) {
            if (max[i] == null) {
                getMax(i);
            }
            if (max[idx - i] == null) {
                getMax(idx - i);
            }
            String value = max[i] + max[idx - i];
            max[idx] = compare(max[idx], value);
        }
        return max[idx];
    }

    private static String compare(String a, String b) {
        if (a.equals(b)) {
            return a;
        } else if (a.length() > b.length()) {
            return a;
        } else if (a.length() < b.length()) {
            return b;
        } else {
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    if (a.charAt(i) > b.charAt(i)) {
                        return a;
                    } else {
                        return b;
                    }
                }
            }
        }
        return a;
    }

    private static void init() {
        max[2] = min[2] = "1";
        max[3] = min[3] = "7";
        max[4] = "11"; min[4] = "4";
        max[5] = "71"; min[5] = "2";
        max[6] = "111"; min[6] = "0";
        max[7] = "711"; min[7] = "8";
        min[8] = "10"; min[9] = "18";
    }
}