[백준/3687] 성냥개비 (Python)

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

3687번: 성냥개비

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:38:41

 

---

 

문제 설명

 

 

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

4
3
6
7
15

 

출력 예시

 

7 7
6 111
8 711
108 7111111

 

 

---

 

풀이

 

큰 수와 작은 수를 구할 때 다른 방식으로 접근해야 한다.

 

제일 큰 수를 구하는 것은 상대적으로 쉽다. 10진수 중 가장 큰 수는 자릿수가 가장 큰 수이므로, 최대한 적은 성냥개비로 최대한 많은 숫자를 그리디하게 만들면 되기 때문이다. 따라서 성냥개비 갯수가 짝수라면 111...111 꼴, 홀수라면 7111...111 ( 가장 작은 홀수인 3으로 나타낼 수 있는 가장 큰 수 7과, 남은 짝수로 만든 1의 집합)꼴로 나타날 수 있다.

 

제일 작은 수를 구하는 작업은 좀 더 심도 있게 DP로 접근하도록 하자. 1자리 숫자로 사용되는 최대 성냥 개수는 7이므로, 2부터 7까지를 가장 작은 숫자 [1, 7, 4, 2, 6, 8]로 초기화할 수 있다.

DP[i]를 i개의 성냥개비로 만들 수 있는 가장 작은 수라고 할 때, 임의의 j (2 <= j <= i-2 )에 대하여

 

DP[i] = min(DP[i], concat(DP[i-j], DP[j]))

 

로 계산된다. 여기서 concat 연산은 두 숫자를 이어붙이는 연산을 의미한다.

여기서 주의해야 할 점은, DP[6] = 6으로 초기화하였으나 이후 연산에서 뒤에서 concat시에는 0으로 취급되어야 한다. 숫자는 0으로 시작할 수 없기 때문에 초깃값을 두번째로 큰 값인 6으로 초기화하였기 때문이다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

dp = [float('inf')]*101
init_list = ['', '', 1, 7, 4, 2, 6, 8]
for i in range(2, 8) :
  dp[i] = init_list[i]

for i in range(8, 101) :
  for j in range(2, i-1) :
    dp[i] = min(dp[i], int(str(dp[j]) + str(dp[i-j])))
    if j == 6 :
      dp[i] = min(dp[i], int(str(dp[i-j]) + '0'))

def find_biggest(num) :
  result = '1'*(num // 2)
  if num % 2 :
    result = '7' + result[1:]
  return result

def find_smallist(num) :
  return dp[num]

T = int(input())
for _ in range(T) :
  N = int(input())
  print(find_smallist(N),  find_biggest(N))

풀이 완료!