[Java] BaekJoon 3678. 성냥개비 (골드2) (DP)

문제출처: https://www.acmicpc.net/problem/3687

3687번: 성냥개비

 

문제이해

 

목표

성냥개비로 십진수 표현

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

주의: 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. 

 

풀이

 

1. 주어진 성냥개비를 모두 사용해 만들 수 있는 작은 수 구하기

결론: DP로 풀이한다. 

dp[] 배열구조: dp[시작0,1][남은 자릿수][남은 성냥개수]

 

왜 첫번째 배열을 0, 1로 나누었는가?

"숫자는 0으로 시작할 수 없다" 는 조건 때문이다. 

DP에 저장된 값을 재활용할 때,
=> 0 (Dp[0]) 으로 시작할때의 최솟값을 이용할 수 있는 경우는,
     맨 앞의 값이 0이 아닌 다른 수로 차있고 그 이후의 값들을 채울 때 이용할 수 있는 경우이다. 
    (맨 앞에서 사용되는 경우는 0으로 시작하는 값을 사용할 수 없다.)
=> 따라서, 1로 시작하는경우는, 0으로 시작하진 않으면서 최솟값을 보장해주는 경우기 때문에 이 (Dp[1]) 값들은 정답을 도출할 때 사용된다.

즉 정리하면 
dp[0][][]:  DP로 재활용되어 적은 탐색을 위해 사용되는 값
dp[1][][]: 1로 시작을 하여 정답도출에 사용 될 수 있는 값

로 역할이 나뉜다.

 이를 0, 1을 toggle이라는 매개변수로 구분한다. 

 

- 클래스와 메소드 부연설명

 

Stick - num (성냥으로 만드는 값)  
        - count (필요한 성냥개수) 

 

initStick()

Stick의 ArrayList를 만들고 이를 num값 기준으로 오름차순 정렬한다. 그럼 0, 1, 2 . . 값 순서로 Stick을 꺼낼 수 있다. 이때, 최솟값을 우선으로 하기 때문에 개수는 겹치지만 값은 작은 3, 9는 필요가 없다. 하지만 Stick(6,6)은 0으로 시작하는 경우가 아닌경우에 필요할 수 있기 때문에 Stick값을 넣어준다. 

getMinDp()

주어진 성냥개수로 최솟값을 구하기 위해 재귀를 활용한다. 최솟값은 숫자가 각 자릿수 별로 하나씩 추가 되기 때문에 String 형으로 값을 추가해야 된다.
정해진 DP값이 있으면 그대로 추가하고, 만약 정해진 DP값이 없으면 조건들 (남은성냥 - 선택한 성냥 < 0  or 뒤에 자릿수가 늘어나게 되면 continue)을 검사해서 통과한 경우 해당 숫자를 최솟값을 만드는데 추가할 수 있는 경우이다. 값을 추가하고 다시 재귀로 다음자릿수에 들어갈 숫자를 찾는다. 

 

2. 주어진 성냥개비를 모두 사용해 만들 수 있는 큰 수 구하기 (규칙 쉽다)

주어진 성냥개비 값(count) 이 짝수이면 count / 2 만큼 1을 추가한 값이 만들 수 있는 가장 큰 수이다.
왜냐하면 자릿수를 최대한 늘려야 큰 수기 때문에

주어진 성냥개비 값이 홀수이면 자릿수는 동일하지만 맨 앞자리가 가능한한 클 수 있으면 좋다.
맨앞에 7을 추가하고 count / 2 - 1 만큼 1을 추가한다. ex) 71111111  

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class 성냥개비 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Stick> sticks;
    private static String[][][] minDp;
    private static String[] maxDp;

    static final int MAX_FIGURE = 16;
    static final int MAX_STICK = 101;

    static class Stick {
        int num; // 값
        int count; // 개수

        public Stick(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        // 개수와 숫자 매칭
        initStick();

        // 알고리즘

        // 최솟값 구하기
        // dp[시작0,1][남은 자릿수][남은 성냥개수]
        minDp = new String[2][MAX_FIGURE][MAX_STICK];
        initMinDp(); // 배열 초기화
        getMinDp();

        // 최댓값 구하기
        maxDp = new String[MAX_STICK];
        getMaxDp();

        // 테스트케이스 결과 도출
        int T = Integer.parseInt(br.readLine());
        for (int testCase = 0; testCase < T; testCase++) {
            int num = Integer.parseInt(br.readLine());
            int figure = (num - 1) / 7 + 1; // 자릿수
            sb.append(minDp[1][figure][num]).append(" ");
            sb.append(maxDp[num]).append("\n");
        }
        System.out.println(sb);
    }

    private static void getMinDp() {
        for (int count = 2; count <= 100; count++) {
            int figure = (count - 1) / 7 + 1; // 자릿수
            minDp[0][figure][count] = getDpValue(0, count, figure, "");
            minDp[1][figure][count] = getDpValue(1, count, figure, "");
        }
    }

    private static void initMinDp() {
        // 최소값 DP 초기화
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < MAX_FIGURE; j++) {
                for (int k = 0; k < MAX_STICK; k++) {
                    minDp[i][j][k] = "";
                }
            }
        }
    }

    private static void getMaxDp() {
        for (int count = 2; count <= 100; count++) {
            int maxLength = count / 2;
            StringBuilder stringBuilder = new StringBuilder();
            if (count % 2 == 0) { // 짝수이면
                for (int j = 0; j < maxLength; j++) {
                    stringBuilder.append(1);
                }
            } else {
                stringBuilder.append(7);
                for (int j = 0; j < maxLength - 1; j++) {
                    stringBuilder.append(1);
                }
            }
            maxDp[count] = stringBuilder.toString();
        }
    }

    // rest 는 남아있는 성냥개비 개수, toggle 은 첫 값이 0으로 시작할지 1로 시작할지 알려주는값
    private static String getDpValue(int toggle, int rest, int figure, String str) {
        if (rest == 0 || figure == 0) {
            return "";
        }
        for (int i = toggle; i < sticks.size(); i++) {
            // 토큰 0일때 dp를 활용
            if (toggle == 0 && !minDp[0][figure][rest].equals("")) {
                return minDp[0][figure][rest];
            } else { // dp 없으면 dfs 로 찾기
                // 숫자 선택
                Stick stick = sticks.get(i);
                // 남은성냥 - 선택한 성냥 < 0 이면 || 뒤에 자릿수가 늘어나게 되면 다시 선택
                if (rest - stick.count < 0 || rest - stick.count > (figure - 1) * 7) {
                    continue;
                }
                // 선택후 다음 자리 탐색
                str += stick.num;
                rest -= stick.count;
                str += getDpValue(0, rest, figure - 1, str);
                break;
            }
        }
        return str;
    }

    private static void initStick() {
        sticks = new ArrayList<>();
        sticks.add(new Stick(1, 2));
        sticks.add(new Stick(7, 3));
        sticks.add(new Stick(4, 4));
        sticks.add(new Stick(2, 5));
        sticks.add(new Stick(0, 6));
        sticks.add(new Stick(6, 6));
        sticks.add(new Stick(8, 7));
        // 3, 9는 사용되지 않음

        Collections.sort(sticks, (a, b) -> {
            return a.num - b.num;
        });
    }
}