백준 3687[자바] java 성냥개비

문제 링크: https://www.acmicpc.net/problem/3687

3687번: 성냥개비

▶문제

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

---

▶입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

---

▶출력

각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.

---

▶해설

DP 문제입니다. 조건을 살펴보겠습니다.

 

1. 각각의 숫자를 만드는데 성냥개비의 개수가 정해져있다.

2. 숫자는 0으로 시작할 수 없다.

3. 가장 작은 수와 가장 큰 수를 만들어라. 

 

0~9까지 숫자를 만드는데 필요한 성냥개비의 수는 아래와 같습니다.

2개 = 1

3개 = 7

4개 = 4

5개 = 2,3,5

6개 = 0,6,9

7개 = 8

 

가장 큰 수를 만드는 것은 쉽게 구할 수 있습니다. 수의 자릿수를 크게 하면 됩니다.

 

1. 주어진 수가 2로 나눠 떨어지다면

-> 몫의 값만큼 1인 String 생성

2. 주어진 수가 2로 나눠 떨어지지 않는다면

-> "7" + 주어진 수 - 3 / 2 몫만큼 1인 String 생성

if(n%2==0){
    sb.append(convertMax(n/2));
}
else{
    sb.append("7").append(convertMax((n-3)/2));
}

private static String convertMax(int n){
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<n; i++){
        sb.append("1");
    }
    return sb.toString();
}

이제 작은 수를 만들어야 합니다. 성냥개비가 6개가 주어졌을 때는 0으로 시작할 수 없으므로 6개로 만들 수 있는 수중 두 번째로 작은 수인 6으로 초기화합니다. 기본 성냥개비의 범위는 2~7이므로 반복문을 간단하게 하기 위해 8개일 때까지 구해줍니다.

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

성냥개비가 9개일 때부터 순차적으로 구하면 됩니다. 

기본 성냥개비의 범위 = 2~7 각각의 값{1,7,4,2,0,8} -> arr []

성냥개비가 9개일 때

String.valueOf(dp [9-2]) + String.valueOf(arr [0]);

String.valueOf(dp [9-3]) + String.valueOf(arr [1]);

...

이런 식으로 구성됩니다. 그랬을 때 가장 작은 값을 넣어주면 됩니다.

for(int i=9; i<=100; i++){
    for(int j=2; j<=7; j++){
        String temp = String.valueOf(dp[i-j])+String.valueOf(arr[j-2]);
        dp[i] = Math.min(Long.parseLong(temp),dp[i]);
    }
}

전체 코드

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

public class Main {
    static long [] dp;
    static int [] arr= {1,7,4,2,0,8};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        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;

        StringBuilder sb;


        for(int i=9; i<=100; i++){
            for(int j=2; j<=7; j++){
                String temp = String.valueOf(dp[i-j])+String.valueOf(arr[j-2]);
                dp[i] = Math.min(Long.parseLong(temp),dp[i]);
            }
        }

        for(int i=0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            sb = new StringBuilder();

            sb.append(dp[n]).append(" ");
            if(n%2==0){
                sb.append(convertMax(n/2));
            }
            else{
                sb.append("7").append(convertMax((n-3)/2));
            }

            System.out.println(sb.toString());
        }
    }

    private static String convertMax(int n){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            sb.append("1");
        }
        return sb.toString();
    }
}