[JAVA] 백준 3687 성냥개비

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

문제분석

성냥개비 갯수가 주어지면, 해당 성냥개비로 만들 수 있는 숫자 최대값/최소값을 구해야한다. Dynamic Programming을 활용해 문제를 해결해야 한다. 이번 문제에서는 index를 '성냥 갯수', 저장하는 값을 'index 성냥갯수로 만들 수 있는 최소값' 이다. 

최대값은? 잘 보면, 최대값은 '자릿수'가 많은게 깡패다. 또한 모든 성냥개비를 다 써야하는 조건때문에 최대값에서 쓰이는 숫자는 7(성냥3개)과 1(성냥2개)밖에 없다. 따라서 홀수일 때 7을 1개만 쓰고, 짝수일 때 1만 써서 수를 나타내면 된다. Greedy로 해결된다.

 

성냥개비 갯수가 n개 주어져서 어떻게 배열 크기를 정해야 하나 할 수 있지만, 문제 조건을 읽어보면 1<n<101이다. 101번의 연산은 시간적으로 부담되는 수치가 아니므로 미리 계산해두고, 필요한 값을 index를 통해 가져오는 방식을 채택했다.

 

점화식은 다음과 같다

minDp[i] = Math.min(minDp[i], minDp[i-숫자 j를 위한 성냥 갯수]*10+숫자 j);

숫자j를 1의 자리에 추가하는 방식으로 101까지 연산을 해나가면 된다.

코드

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

public class Main {
    static int[] nums = {6,2,5,5,4,5,6,3,7,6}; // 인덱스가 숫자, 값이 성냥개비 갯수
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        long[] minDp = new long[101];
        Arrays.fill(minDp, Long.MAX_VALUE);
        minDp[2]=1;
        minDp[3]=7;
        minDp[4]=4;
        minDp[5]=2;
        minDp[6]=6;
        minDp[7]=8;
        minDp[8]=10;

        for(int i = 9; i < 101; i++){
            for(int j = 0; j<10; j++){
                if(i>nums[j]){
                    minDp[i] = Math.min(minDp[i], minDp[i-nums[j]]*10+j);

                }
            }
        }

        for(int i = 0; i < N; i++){
            int count = Integer.parseInt(br.readLine());// 성냥개비 갯수(전부 사용해야 함)
            long minResult = minDp[count];
            String maxResult = "";
            int high = count / 2; // 몫.
            int low = count % 2; //홀수면 1, 짝수면 0
            for(int j = 0; j<high-1;j++){
                maxResult+="1";
            }
            maxResult = (low==1?"7":"1") + maxResult;
            bw.write(minResult+" "+maxResult);
            bw.newLine();
        }
        bw.flush();
        bw.close();

        
    }
}