[BaekJoon] 3687 성냥개비 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int SIZE = 100;
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    static int n;
    static String[] max;
    static long[] min;

    static void input() {
        n = scanner.nextInt();
    }

    static void solution() {
        sb.append(min[n]).append(' ').append(max[n]).append('\n');
    }

    static void calcAllCase() {
        calcAllMin();
        calcAllMax();
    }

    static void calcAllMin() {
        min = new long[SIZE + 1];
        Arrays.fill(min, Long.MAX_VALUE);

        min[0] = min[1] = 0;
        min[2] = 1;
        min[3] = 7;
        min[4] = 4;
        min[5] = 2;
        min[6] = 6;
        min[7] = 8;
        min[8] = 10;

        String[] num = {"1", "7", "4", "2", "0", "8"};

        for(int idx = 9; idx <= SIZE; idx++) {
            for(int count = 2; count <= 7; count++) {
                String minNum = min[idx - count] + num[count - 2];
                if(Long.parseLong(minNum) == 0) continue;
                min[idx] = Math.min(Long.parseLong(minNum), min[idx]);
            }
        }
    }

    static void calcAllMax() {
        max = new String[SIZE + 1];

        max[2] = "1";
        for(int idx = 3; idx <= SIZE; idx++) {
            String maxNum = "";
            if(idx % 2 == 0) {
                for(int num = 0; num < idx / 2; num++) maxNum += "1";
            } else {
                int remain = idx - 3;
                maxNum += "7";
                for(int num = 0; num < remain / 2; num++) maxNum += "1";
            }

            max[idx] = maxNum;
        }
    }

    public static void main(String[] args) {
        calcAllCase();

        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }

        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 가능한 최대 성냥 개수가 100개이기 때문에 100개까지 각 성냥을 가지고 만들 수 있는 최솟값과 최댓값을 미리 구하고 이를 이용하여 최솟값 및 최댓값을 구합니다.
  • 최댓값을 생각해보면 1과 7만을 이용하여 만들면 됩니다.
    • 만약 n이 짝수라면 1을 가지고만 만들고, n이 홀수라면 1과 7을 이용하여 최댓값을 만듭니다.
      • 결국 큰 수를 만들기 위해서는 자릿수를 최대로 만들고 자릿수가 같다면 수를 같게 만들어야하는데, 1과 7만을 이용하는 것이 자릿수를 최대로 만들 수 있습니다.
      • 홀수일 때는 최대한 수를 많이 사용하기 위해 7은 한 개만 사용하고 나머지는 1로만 사용하며, 가장 큰 수를 만들기 위해 가장 큰 자리수를 7로 합니다.
  • 최솟값을 구할 때는 이전까지 구한 최솟값을 이용하여 구합니다.
    • 우선 성냥 개수가 0, 1일 때는 만들 수 있는 수가 없으므로 0으로 초기화합니다.
    • 성냥 개수가 2부터 7 이하일 때는 해당 성냥 개수들을 이용해서 한 자리 수를 만들 수 있기 때문에 이 수들이 최솟값이 됩니다.
    • 성냥 개수가 5, 6일 때는 만들 수 있는 한 자리 수가 여러 개가 될 수가 있는데, 최솟값을 만들어야 하기 때문에 그 중 가장 작은 값을 최솟값으로 하는데, 0이 포함된 성냥 개수가 6인 경우는 양수여야 하고 숫자는 0으로 시작할 수 없으므로 그 다음으로 작은 수인 6을 최솟값으로 합니다.
    • 그러나 두 자리수 이상을 만들 때에는 0을 쓸 수 있기 때문에 이후에 가장 큰 자리수가 아닌 다른 자리수에 사용할 때에는 성냥 6개에 대한 최솟값을 0으로 활용합니다.
    • 성냥 개수가 9개 이상일 때는 이전의 최솟값에 수 하나를 붙여 최솟값을 구합니다.
    • 한 자리 수를 만들 수 있는 성냥 개수는 2 이상 7 이하이기 때문에 각 경우에 대해 모두 최솟값을 구해보고 그 중 가장 작은 값을 선택합니다.