[백준] 성냥개비 3687번 (java)

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

풀이 방법

각 수를 만드는데 필요한 성냥개비의 수를 알아보자

1 = 2개

2 = 5개

3 = 5개

4 = 4개

5 = 5개

6 = 6개

7 = 3개

8 = 7개

9 = 6개

0 = 6개

 

가장 큰 수를 만드는 것은 가장 자릿수가 많아야 한다.

가장 자리수가 많기 위해선 가장 작게 성냥개비를 사용할 수 있는 수를 최대한 많이 추가해야 하는데

필요한 성냥의 수를 보면 너무 좋게 2개를 사용해서 1, 3개를 사용해서 7을 만들 수 있어 그리디 하게 풀방법을 생각해 낼 수 있었다.

만약 주어진 성냥개비수가 홀수이면 맨 앞을 7로 나머지 뒤는 모두 1로, 반대로 짝수이면 모든 수를 1로 채워 넣으면 가장 큰 자릿수를 만들 수 있고 이것이 가장 큰 수가 된다.

 

가장 작은 수도 처음엔 그리디 하게 풀 수 있을 거 같아 처음부터 dfs탐색으로 가장 많은 성냥개비를 사용할 수 있는 방법으로 채워나가려고 했다. 예시로 가장 많은 성냥개비를 사용하는 8부터(7개 사용) 다음엔 6개 사용하는 수 중 가장 작은 0을 사용 이렇게 dfs + 백트레킹으로 탐색하며 성냥개비의 수가 딱 맞아 떨어지는 수가 정답이 될 것이라고 생각했으나 예외가 존재했다.

 

예외) 17개가 주어지는 경우 788이 나오지만 정답은 200이 된다.

 

그러므로 그리디하게 풀 수 없고, 메모리제이션을 이용한 완전 탐색으로 풀이해야 했다.

 

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

 

위와 같이 메모리제이션 배열을 초기화한다.

static int[] small_arr = {0, 0, 1, 7, 4, 2, 0, 8};

그 후 성냥개비 개수에서 사용할 수 있는 수중 작은 수를 배열에 저장한다. (ex 2개 사용 -> 1만 듦 idx = 2자리에 1 할당)
그 후 dp [i] = min(dp [i], dp [i-j] + small_arr [j])로 표현할 수 있다.

여기서 small_arr [j] + dp [i-j]와 dp[i-j] + small_arr [j]를 고민했다. 여기서  전자를 사용하게 된다면 성냥개비가 6개인 경우 0이 앞자리에 와서 런타임 에러가 발생하기 때문에 후자를 선택해야 한다.

 

import java.io.*;
import java.util.*;


public class P_3687 {

    static int[] small_arr = {0, 0, 1, 7, 4, 2, 0, 8};
    static Long[] dp = new Long[101];

    static int n;
    static String big_num(int num) {
        StringBuilder sb = new StringBuilder();
        int cnt = num / 2;
        if (num % 2 == 1) {// 홀수 인경우
            sb.append("7");
        }
        else {
            sb.append("1");
        }
        for (int i = 0;i < cnt - 1;i++) {
            sb.append("1");
        }
        return sb.toString();
    }
    public static void findSmallNum() {
        dp[2] = 1L;
        dp[3] = 7L;
        dp[4] = 4L;
        dp[5] = 2L;
        dp[6] = 6L;
        dp[7] = 8L;
        dp[8] = 10L;

        for (int i = 9;i < 101;i++) {
            for (int j = 2;j < 8; j++) {
                StringBuilder sb = new StringBuilder(Long.toString(dp[i-j]) + Long.toString(small_arr[j]));
                dp[i] = Math.min(dp[i], Long.parseLong(sb.toString()));
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        Arrays.fill(dp, Long.MAX_VALUE);
        int num;
        findSmallNum();
        for (int i = 0;i < n;i++) {
            num = Integer.parseInt(br.readLine());
            String big_ans = big_num(num);
            System.out.println(dp[num] + " " + big_ans);
        }
    }
}