bj3687(그리디, dp) - 성냥개비

어려운 문제였다.

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

우선, 한 문제 안에 dp와 그리디가 들어간다.

 

1. 최소 자릿수 찾기

1차원 배열을 만들고, 2개~7개의 성냥을 썻을때, 최소 값을 dp로 구한다.

cnt개일 때, 최솟값을 구한다.

 

2. 최대 자릿수 찾기

사실상, 그리디가 아니다.

그저 성냥 2개를 써서 자릿수를 가장 크게 만드는 것이다.

 

 

=> 나는 Math.pow를 써서 그냥 long으로 만들어주었는데, 계속 런타임에러가 떠서 보니, long도 초과하는 크기였다.

=> pow가 쓸일이 있을때는 그냥 StringBuilder로 만들어주는게 좋을 것 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int T;
    static StringBuilder stringBuilder = new StringBuilder();
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        for(int i = 0; i < T; i++){
            String[] answer = solve(Integer.parseInt(bufferedReader.readLine()));
            stringBuilder.append(answer[0] + " " + answer[1]).append("\n");
        }
        System.out.println(stringBuilder);
    }

    private static String[] solve(int cnt) {
        return new String[]{findMin(cnt), findMax(cnt)};
    }

    private static String findMin(int cnt) {   //최소 자릿수 찾기
         long[] dp = new long[101];
        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;
         String[] add = {"1", "7", "4", "2", "0", "8"};
         for(int i = 9; i <= 100; i++){
             for(int j = 2; j < 8; j++){
                 if(dp[i-j] == Long.MAX_VALUE)continue;
                 String line = dp[i - j] + add[j - 2];
                 dp[i] = Math.min(Long.parseLong(line), dp[i]);
             }
         }
         return dp[cnt] + "";
    }


    private static String findMax(int cnt) {   //최대 자릿수 찾기
        String answer = "";
        StringBuilder line = new StringBuilder();
        if(cnt % 2 == 1){
            int oneSize = cnt / 2 - 1;
            while(oneSize-- > 0){
                line.append("1");
                cnt -= 2;
            }
            line.insert(0, "7");
            answer = line.toString();
        }else{
            int oneSize = cnt / 2;
            while(oneSize-- > 0){
                line.append("1");
            }
            answer = line.toString();
        }
        return answer;
    }

    private static void initialize() throws IOException {
        T = Integer.parseInt(bufferedReader.readLine());
    }
}