[백준] 성냥개비(3687) - java

문제 설명 :

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

 

문제 요약 :

1. 주어진 성냥개비를 모두 써서 만들 수 있는 가장 작은 수와, 가장 큰 수 구하기

 

 

문제 풀이 시간 : 1시간 30분

문제 성공 여부 : 성공

 

접근 방법(성공) :

1. 큰 수 구하기

큰 수 구하기는 매우 간단하다.

수의 크기를 늘리기 위해서 가장 쉬운 방법은 자릿수를 늘리는 방법이다.

 

1은 성냥 2개로 만들 수 있는 가장 큰 수이므로, n/2개의 1을 만들 수 있다.

예를 들어, 9라는 수가 있으면 9/2 = 4 이므로 1111을 만들 수 있다.

하지만, 이 경우 성냥개비가 1개가 남게 되고, 더 이상의 숫자를 만들 수 없다.

 

따라서, 성냥을 2개보다 더 사용해서 1이 아닌 다른 수를 만들어서 나머지 값이 없도록 만들어야 한다.

성냥 3개를 사용하면 7을 만들 수 있기 때문에 n%2==1 인 경우, 3을 추가하고 나머지 값/2만큼의 1을 추가해 주면 된다.

 

따라서, 9는 9%2==1 이므로, 3개를 먼저 사용해서 7을 만든다.

이제 6개가 남았으므로, 6/2 = 3이므로 7111이라는 수를 만들 수 있다.

이 수가 가장 자릿수가 높으며 주어진 성냥으로 만들 수 있는 가장 큰 수가 된다.

 

가장 큰 수 만들기 함수

    String big(int num){
        String number = "";
        
        if(num%2 == 1){ // 2를 나눈 나머지가 1일 경우, 3개를 사용해서 7을 만든다.
            number += "7";
            num-=3;
        }
        for(int i=0; i<num/2; i++){ // 나머지 성냥을 사용해서 1을 만든다.
            number += "1";
        }
        return number;
    }

 

 

2. 가장 작은 수 만들기

가장 작은 수 만들기는 큰 수 만들기와 달리 특별한 규칙이 없다.

하지만, 우린 2~7가지의 성냥을 사용해서 0~9라는 수를 만들 수 있다.

 

성냥 개수 별 만들 수 있는 숫자들
2 : 1
3 : 7
4 : 4
5 : 2   , 3, 5
6 : 0   , 6, 9
7 : 8

 

이처럼, 2~7가지의 성냥으로 만들 수 있는 가장 작은 값들의 정보가 있으므로 우린, dp를 통해 문제에 접근할 수 있다.

 

8개의 성냥을 사용해서 가장 작은 수를 만드려면 어떻게 할 수 있을까?

 

우선, 숫자 하나를 만들 방법은 없기 때문에 두 가지 이상의 숫자를 조합해야 한다.

 

8개의 성냥을 두 가지의 숫자로 조합하는 경우는 다음과 같다.

 

2개 + 6개 -> 1 0

3개 + 5개 -> 7 2

4개 + 4개 -> 4 4

5개 + 3개 -> 2 7

6개 + 2개 -> 6 1

 

이 중 가장 작은 수는 2개 + 6개를 결합한 10이 된다!

 

이제 감이 어느 정도 잡힐 것이라고 생각한다.

하나의 예시만 더 해보겠다.

 

9개의 성냥을 두 가지의 숫자로 조합하는 경우는 다음과 같다.

 

2개 + 7개 -> 1 8

3개 + 6개 -> 7 0

4개 + 5개 -> 4 2

5개 + 4개 -> 2 4

3개 + 6개 -> 6 7

2개 + 7개 -> 8 1

 

그렇다. 2부터 n-2까지 모든 조합을 만든 후 가장 작은 수를 찾으면 dp[n]의 가장 작은 수를 알 수 있게 된다!

 

가장 작은 수 만들기 함수

        long[] dp = new long[101];
        dp[2] = 1;
        dp[3] = 7;
        dp[4] = 4;
        dp[5] = 2;
        dp[6] = 0;
        dp[7] = 8;

        for(int i=8; i<=100; i++){
            long min = Long.MAX_VALUE; // int 범위를 넘어가기 때문에 long으로 한다.

            for(int j=2; j<i-1; j++){ // 2~i-2까지 모든 조합을 탐색한다.
                String s = "";
                int a = j; // 2, 3, ...
                int b = i-j; // n-2, n-3, ...

                if(a==6) s+= "6"; // 가장 앞에는 0이 올 수 없기 때문에 "6"으로 변경해준다.
                else s+= dp[a]; // a에 대한 dp값을 먼저 붙여준다.
                
                s += dp[b]; // 이후 b에 대한 dp값을 뒤에 붙여준다.

                long num = Long.parseLong(s); // 대소비교를 위해 문자열을 long 타입으로 변경해준다.
                min = Math.min(min, num); // 대소 비교
            }
            
            dp[i] = min; // 가장 작은 값을 dp에 저장
        }

 

 

전체 코드(성공) :

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        long[] dp = new long[101];
        dp[2] = 1;
        dp[3] = 7;
        dp[4] = 4;
        dp[5] = 2;
        dp[6] = 0;
        dp[7] = 8;

        for(int i=8; i<101; i++){
            long min = Long.MAX_VALUE;

            for(int j=2; j<i-1; j++){
                String s = "";
                int a = j;
                int b = i-j;

                if(a==6) s+= "6";
                else s+= dp[a];
                s += dp[b];

                long num = Long.parseLong(s);
                min = Math.min(min, num);
            }
            dp[i] = min;
        }

        for(int i=0; i<T; i++){
            int num = Integer.parseInt(br.readLine());

            String a = Long.toString(dp[num]);
            if(num==6) a="6"; // dp[6]은 0이므로 6으로 변경!
            
            String b = big(num);
            System.out.println(a + " " + b);
        }
    }

    static String big(int num){
        String number = "";
        if(num%2 == 1){
            number += "7";
            num-=3;
        }
        for(int i=0; i<num/2; i++){
            number += "1";
        }
        return number;
    }

}