BOJ_3687_성냥개비 (Java)

[Gold II] 성냥개비 - 3687

문제 링크

성능 요약

메모리: 14060 KB, 시간: 104 ms

분류

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

제출 일자

2025년 3월 31일 22:01:50

문제 설명

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

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

입력

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

출력

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

문제 풀이

45분 소요

코드

/**
 * Author: nowalex322, Kim HyeonJae
 * 21:15 ~ 22:05
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static int[] nums = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 0~9 성냥개수
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_3687_성냥개비/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long[] dp = new long[101]; // min계산 // 100 = 14*7 + 2 -> 최대15자리 -> long
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[2] = 1;
        dp[3] = 7;
        dp[4] = 4;
        dp[5] = 2;
        dp[6] = 6;
        dp[7] = 8;
        dp[8] = 10;
        dp[9] = 18;
        dp[10] = 22;

        // DP 계산 - 최소값 구하기
        for (int i = 11; i <= 100; i++) {
            for (int num = 0; num < 10; num++) {
                if (i - nums[num] >= 2 && dp[i - nums[num]] != Long.MAX_VALUE) { // 자릿수추가 (앞 or 뒤)
                
                    // 0
                    if(num == 0) dp[i] = Math.min(dp[i], dp[i-nums[num]] * 10L);

                    else{
                        long tmp1 = dp[i - nums[num]] * 10L + num;
                        long tmp2 = num * (long) Math.pow(10, digitCnt(dp[i-nums[num]])) + dp[i-nums[num]];

                        dp[i] = Math.min(dp[i], Math.min(tmp1, tmp2));
                    }
                }
            }
        }

        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());

            StringBuilder sb = new StringBuilder();

            //min
            sb.append(dp[n]).append(" ");

            //max
            if(n%2 == 1){
                sb.append(7);
                for(int i=0; i<(n-3)/2; i++){
                    sb.append(1);
                }
            }
            else{
                for(int i=0; i<n/2; i++){
                    sb.append(1);
                }
            }
            sb.append("\n");
            bw.write(sb.toString());
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private int digitCnt(long num){
        if(num==0) return 1;
        return (int) Math.log10(num) + 1;
    }
}