백준 3687번: 성냥개비

문제 설명

• https://www.acmicpc.net/problem/3687
• 성냥을 N개 사용해서 만들 수 있는 숫자의 최댓값과 최솟값을 구하는 문제입니다.

접근법

• 성냥 100개로 모두 1을 만들 경우 1이 50개 생깁니다. 이는 Long을 초과하는 아주 큰 숫자이므로 String 혹은 BigInteger로 처리해야 합니다. 저는 BigInteger를 사용했습니다.
  • BigInteger에 문자열 합치기가 없어 String으로 변환한 뒤 다시 BigInteger로 선언했습니다.
    BigInteger num = new BigInteger(dpMin[i-key].toString() + graph.get(key).get(0)).toString();
  • BigInteger의 크기비교는 compareTo를 통해 가능합니다.
• 최댓값을 구하는 배열과 최솟값을 구하는 배열을 따로 만들어 정답을 구했습니다.
• 최솟값에서는 숫자는 0으로 시작할 수 없다는 조건을 고려해야 합니다.
  • 성냥을 6개 사용할 때 0이 더 적지만 0이 아닌 6을 선택해야 합니다.
  • 이후 모든 경우에서 6을 쓰는것보다 0을 쓰는게 무조건 최솟값에 가깝습니다.(6은 더이상 사용하지 않습니다.)

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		HashMap<Integer,List<String>> graph = new HashMap<Integer,List<String>>(); // 사용되는 성냥 : [기본으로 만들 수 있는 숫자들]
		List<String> temp = new ArrayList<String>();
		temp.add("1");
		graph.put(2, temp);
		
		temp = new ArrayList<String>();
		temp.add("7");
		graph.put(3,temp);

		temp = new ArrayList<String>();
		temp.add("4");
		graph.put(4, temp);
		
		temp = new ArrayList<String>();
		temp.add("2");
		temp.add("3");
		temp.add("5");
		graph.put(5, temp);
		
		temp = new ArrayList<String>();
		temp.add("0");
		temp.add("6");
		temp.add("9");
		graph.put(6, temp);
		
		temp = new ArrayList<String>();
		temp.add("8");
		graph.put(7, temp);
//		System.out.println(graph.toString());
		
		// 최댓값
		BigInteger[] dpMax = new BigInteger[101];
		dpMax[2] = new BigInteger("1");
		dpMax[3] = new BigInteger("7");
		dpMax[4] = new BigInteger("11");
		dpMax[5] = new BigInteger("71");
		dpMax[6] = new BigInteger("111");
		dpMax[7] = new BigInteger("711");
		dpMax[8] = new BigInteger("1111");
		for (int i = 9; i <= 100; i++) {
			for (int key : graph.keySet()) {
				BigInteger num = new BigInteger(dpMax[i-key].toString() + graph.get(key).get(graph.get(key).size()-1));
				if(dpMax[i-key] != null 
						&& (dpMax[i] == null || dpMax[i].compareTo(num) < 0)) {
					dpMax[i] = num;
				}
			}
		}
		
		// 최솟값
		BigInteger[] dpMin = new BigInteger[101];
		dpMin[2] = new BigInteger("1");
		dpMin[3] = new BigInteger("7");
		dpMin[4] = new BigInteger("4");
		dpMin[5] = new BigInteger("2");
		dpMin[6] = new BigInteger("6");
		dpMin[7] = new BigInteger("8");
		dpMin[8] = new BigInteger("10");
		for (int i = 9; i <= 100; i++) {
			for (int key : graph.keySet()) {
				BigInteger num = new BigInteger(dpMin[i-key].toString() + graph.get(key).get(0).toString());
				if(dpMin[i-key] != null 
						&& (dpMin[i] == null || dpMin[i].compareTo(num) > 0)) {
					dpMin[i] = num;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < T; t++) {
			int num = Integer.parseInt(br.readLine());
			sb.append(dpMin[num]);
			sb.append(" ");
			sb.append(dpMax[num]);
			sb.append("\n");
		}
		System.out.println(sb.toString());
		
	}

}