[BOJ/백준] 3687 성냥개비

import sys

def input():
    return sys.stdin.readline()

N = int(input())
INF = float('inf')
dp = [INF for _ in range(101)]
dp[2] = 1
dp[3] = 7
dp[4] = 4
dp[5] = 2
dp[6] = 6
dp[7] = 8
dp[8] = 10

for num in range(9,101):
    for i in range(2,8):
        if i != 6:
            dp[num] = min(dp[num],dp[num-i]*10+dp[i])
        else:
            dp[num] = min(dp[num],dp[num-i]*10)
for _ in range(N):
    k = int(input())
    
    max_value = ('7' if k%2 else '1' ) +'1'*(k//2-1)
    print(dp[k],max_value)

 

이 문제를 푸는 방식은 다음과 같다.

 

2개부터 8개까지의 성냥개비를 이용해서 만들 수 있는 최소의 수가 있다.

 

먼저 이 수들을 각각 저장을 해주는 것이다.

 

단 여기서 주의해야할 점은 성냥개비의 개수가 6개일때다.

 

6개일때는 원래 최저의 수는 0이지만, 자리수가 1개일때 0이 올수가 없다. 이 점만 주의해주면 된다.

 

이렇게 2~8개의 최소 숫자를 구해주고

 

9개부터는 그리디하게 찾아주면 된다.

 

 

dp [ 현재 성냥의 개수 - i개 ] *10 + dp[i] 와 dp[현재 성냥의 개수] 의 최소값을 비교해서 갱신해주면 된다.

 

그리고 위에 말했듯이 6개일때는 가장 작은 수는 0 이므로 *10만 해주면 된다.

 

이렇게 최소 숫자를 구했으면,

 

최대 숫자를 구해야한다.

 

여기서 가장 큰 숫자를 만드는 법은 가장 적은 개수로 만들수 있는 1로 채우는 것이다.

 

그런데 이럴때 문제는 성냥의 개수가 홀수일때 문제가 된다.

 

성냥의 개수가 홀 수 일때 1개가 남아서, 어떠한 숫자도 만들수 없다.

 

그러므로 주어진 성냥개비의 숫자가 홀수이면, 가장 앞의 수를 1이 아닌 성냥개비 3개로 만들수 있는 가장 큰수를 만들어줘야한다.

 

그에 부합하는 숫자는 7 이므로,

 

주어진 성냥 개비의 숫자가 홀수이면 7 아니면 1을 붙이고, 성냥개비를 2로 나눈 몫에서 1을 뺀숫자만큼 붙여주면 된다.