백준 3687 성냥개비(DP, 그리디)

3687번: 성냥개비

가장 큰 수

- 111111xxxxx
- 성냥 개수가 홀수면 3개(7) 쓰고 나머지 2개(1)로 이어붙이기

가장 작은 수

- xxxx888888

- 성냥을 많이 쓰면서 자리수를 최대한 줄여야 된다

DP Table에 min값을 저장한다

2 ~ 9까지 만들 수 있는 애들을 Queue에 넣고 성냥을 1~10까지 넣어 볼 수 있는 경우 다 넣는다

package pratice;

import java.util.*;

class Data{
    int cnt;
    long num;

    public Data(int cnt, long num){
        this.cnt = cnt;
        this.num = num;
    }

    @Override
    public String toString() {
        return cnt + "" + num;
    }
}
public class Main_3687 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();


        int[] num_data = {6,2,5,5,4,5,6,3,7,6};
        long[] dp = new long[101];
        for (int i = 0; i < 101; i++) {
            dp[i] = Long.MAX_VALUE;
        }

        Queue<Data> queue = new ArrayDeque<>();
        for (int j = 1; j < 10; j++) {
            queue.add(new Data(num_data[j],j));
        }

        while(!queue.isEmpty()){
            Data temp = queue.poll();
            int cnt = temp.cnt;
            long num = temp.num;
            dp[cnt] = Math.min(dp[cnt], num);

            if (dp[cnt] != num)
                continue;
            for (int j = 0; j < 10; j++) {
                if ((cnt+num_data[j]) <= 100){
                    queue.add(new Data(cnt+num_data[j],Long.parseLong(num+""+j)));
                }
            }
        }


        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            StringBuilder sb = new StringBuilder();

                //가장 작은 수
                sb.append(dp[N]+" ");

                //가장 큰 수
                //성냥 개수가 홀수면 3개(7) 쓰고 나머지 2개(1)로 이어붙이기
                if (N == 3){
                    sb.append("7");
                }
                else{
                    if (N % 2 == 1){
                        sb.append("7");
                        for (int j = 0; j < (N-3)/2; j++) {
                            sb.append("1");
                        }
                    }
                    else{
                        for (int j = 0; j < N/2; j++) {
                            sb.append("1");
                        }
                    }
                }
            System.out.println(sb.toString());

        }
        }

    }