[백준 3687 🥇] 성냥개비

문제

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

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

입력

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

출력

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

문제 풀이

import sys

t=int(sys.stdin.readline())
# 성냥개비 개수별로 만들 수 있는 가장 작은 수
# 2~7
# numbers=['','','1','7','4','2','0','8']
numbers=[0,0,1,7,4,2,0,8]
# 가장 작은 수 구하기
#dp=['9999999999999999999']*(101)
dp=[sys.maxsize]*(101)
# dp init
for i in range(2,8):
    if i==6:
        # dp[i]='6'
        dp[i]=6
    else:
        dp[i]=numbers[i]
for idx in range(8,101):
    for j in range(2,8):
        # if int(dp[idx])>int(dp[idx-j]+numbers[j]):
            # dp[idx]=dp[idx-j]+numbers[j]
        dp[idx]=min(dp[idx], dp[idx-j]*10+numbers[j])

for _ in range(t):
    num=int(sys.stdin.readline())
    # 가장 큰 수 구하기
    largest=''
    # 홀수일 경우
    if num%2==1:
        largest+='7'
        largest+='1'*(num//2-1)
    else:
        # 짝수일 경우
        largest+='1'*(num//2)
    smallest=dp[num]
    print(smallest, largest)

• Greedy와 DP를 합쳐놓은 문제였다.
• 먼저 n개의 성냥개비로 만들 수 있는 최댓값은 아이디어를 떠올리기 쉽다. 단순히 만들 수 있는 수의 자릿수를 제일 길게 늘려주면 해당 값이 최댓값이 된다. 
  • 가장 적은 수의 성냥 개비(2개)로 만들 수 있는 수 '1'로 최대한 자릿수를 늘려준다.
  • 성냥개비의 개수 num이 짝수일 경우, num//2한 만큼 '1'로 채워주면 된다.
  • num이 홀수일 경우, 첫 번째 자리만 성냥개비가 3개 필요한 '7'로 채워주고 나머지 자릿수는 모두 '1'로 채워준다.
    • '7'+'1'*(num//2-1)
• n개의 성냥개비를 만들 수 있는 최솟값은 DP를 이용해서 풀면 된다.

• 성냥개비 개수별로 만들 수 있는 수의 가장 작은 값을 numbers 배열에 저장한다.
  • 예를 들어, numbers[2]는 성냥개비 2개로 만들 수 있는 가장 작은 수이므로 1이 저장된다. 
  • 또, numbers[6]는 성냥개비 6개로 만들 수 있는 가장 작은 수이므로 0이 저장된다.
• 파이썬의 정수 최댓값이 저장된 sys.maxsize로 dp 배열을 초기화한다.
  • dp[n]은 n개의 성냥개비로 만들 수 있는 가장 작은 수이다.
  • 처음엔 습관처럼 1e9로 초기화했다가, 나중에 10000088888 이런 수가 나와서 1e9로 초기화해서는 올바르게 min 연산을 수행하지 못해서 sys.maxsize로 초기화했다. (약 9경 정도의 숫자라고 한다..)
• dp[2]~dp[7]까지는 dp[6]를 제외하고, 모두 한자리 수가 가장 작은 값으로, numbers 배열 값과 동일하다.
  • dp[6]는 수의 가장 앞 자리에 0이 올 수 없으므로 numbers[0]이 아니라 6으로 초기화해줘야 한다.
• dp[8]부터 dp[100]까지 for문을 돌면서 numbers 배열에 저장된 한 자리수를 나타낼 수 있는 성냥의 개수 2~7개를 하나씩 넣어보면서 최솟값을 갱신한다.
  • 예를 들면, 아래 그림과 같다. 

• 이와 같이 성냥개비 개수가 100일 때까지 모든 dp 배열을 채우고, n을 입력받을 때마다 dp[n] 값을 출력해주면 된다.