백준 3687

3687번: 성냥개비

---

문제

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

!https://www.acmicpc.net/upload/images/match.png

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

입력

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

출력

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

제한

• 시간 제한 : 1초
• 메모리 제한 : 128MB

---

문제 풀이 과정

성냥 개비를 모두 사용해서 제일 크게 만드는 방법은 7과 1을 사용하는 방법이다. 7은 3개가 들고, 1은 2개가 들기 때문이다.

즉, 가장 긴 자릿수를 만들면 되는데, 만약 n이 홀수이면 3개를 사용해 7을 하나 넣고, 나머진 1로 채우면되고, n이 짝수이면 젤 긴자리를 만들 수 있는 1로 모두 채우는 방법을 사용하면 된다.

제일 작게 만드는 방법은 다음과 같다.

만약 9개를 사용해 제일 작은수를 만든다고 하면 다음 경우의 수가 생긴다.

2 + 7, 3 + 6, 4 +5 , 5+4, 6+3, 7+2

즉 2개 ~ 7개를 사용하는 방법을 모두 계산해 보면 된다.

---

정답 코드

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

class Main3687 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		long[] dp = getMin();

		while (T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			String max = getMax(N);

			sb.append(dp[N]).append(' ').append(max).append('\\n');
		}
		System.out.println(sb);
	}

	//제일 작게 만드는 방법
	//D[i] = i개의 성냥개비를 사용하여 만들 수 있는 제일 작은 수
	private static long[] getMin() {
		long[] d = new long[101];

		Arrays.fill(d, Long.MAX_VALUE);
		d[2] = 1;
		d[3] = 7;
		d[4] = 4;
		d[5] = 2;
		d[6] = 6;
		d[7] = 8;
		d[8] = 10;

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

		for (int i = 9; i <= 100; i++) {
			for (int j = 2; j <= 7; j++) {
				String s = d[i - j] + minNumberUseMatchstick[j - 2];
				d[i] = Math.min(Long.parseLong(s), d[i]);
			}
		}

		return d;
	}

	//제일 크게 만드는 방법
	//2개씩 나눠서 1로 만든다, 나머지가 있다면 몫에서 -1 해서 3개를 만든다.
	private static String getMax(int n) {
		StringBuilder sb = new StringBuilder();
		int cnt = n / 2;
		if (n % 2 != 0) {
			cnt--;
			sb.append(7);
		}

		for (int i = 0; i < cnt; i++) {
			sb.append(1);
		}

		return sb.toString();
	}
}