[BOJ] 성냥개비 (3687, G2)

문제풀이 아이디어

각 숫자마다 쓰이는 성냥개비가 달라서, 명백하게 어떤 일반항을 찾기는 어렵지만 어느 정도 통제가 가능합니다.

같은 개수가 사용된 성냥개비 중 최댓값을 만들기 위해서는 가장 큰 숫자, 최솟값을 만들기 위해서는 가장 작은 숫자가 필요합니다.

단! 최솟값의 경우 맨 앞에 0이 와서는 안됩니다. 따라서 6으로 대체하고, 맨 앞이 아닌 6은 모두 0으로 대치하는 별도의 추가 과정이 필요합니다.

근데 이걸 그냥은 알기가 어렵습니다. 최초 2~7획에서도 최대/최소의 케이스가 달라지므로 다음과 같이 생각합니다.

먼저 2, 3개는 그냥 초항으로 계산합니다.
4개째부터는 2~7획이전의 결과를 살펴보아, 그냥 자체로 최대/최소인지, 이전의 결과에 특정 숫자를 앞뒤로 붙여 최대/최소인지 모두 확인합니다. 그리고 가장 큰 값을 계속 이어갑니다. 가장 커야 그 뒤에 숫자를 붙일때도 가장 커집니다.

즉, DP + 그리디 문제입니다. 

코드

import sys
input = sys.stdin.readline

Q = int(input())
max_digit_cnt = {2: 1, 3: 7, 4: 4, 5: 5, 6: 9, 7: 8}
min_digit_cnt = {2: 1, 3: 7, 4: 4, 5: 2, 6: 6, 7: 8} # 6은 6 or 0으로 사용해야함에 주의 최솟값 어려움.
min_dp = [0] * 101
max_dp = [0] * 101

for i in range(2, 101):
    if i == 2:
        min_dp[i] = 1
        max_dp[i] = 1
    elif i == 3:
        min_dp[i] = 7
        max_dp[i] = 7
    else:
        prev_check = [2, 3, 4, 5, 6, 7]
        # 최솟값 관련
        min_list = []
        if i in prev_check:
            min_list.append(min_digit_cnt[i])
        for p in prev_check:
            if i-p >= 2:
                cur_prev = min_dp[i-p]
                cur_add = min_digit_cnt[p]
                cur_front = cur_prev * 10 + cur_add # prev를 앞에 붙이는 경우
                cur_back = cur_add * (10 ** len(str(cur_prev))) + cur_prev # 뒤로 붙이는 경우
                min_list.append(min(cur_front, cur_back))
        cur_min = list(str(min(min_list)))
        for j in range(1, len(cur_min)):  # 0 보정 코드
            if cur_min[j] == '6':
                cur_min[j] = '0'
        min_dp[i] = int(''.join(cur_min))

		#최댓값 관련
        max_list = []
        if i in prev_check:
            max_list.append(max_digit_cnt[i])
        for p in prev_check:
            if i-p >= 2:
                cur_prev = max_dp[i-p]
                cur_add = max_digit_cnt[p]
                cur_front = cur_prev * 10 + cur_add # prev를 앞에 붙이는 경우
                cur_back = cur_add * (10 ** len(str(cur_prev))) + cur_prev # 뒤로 붙이는 경우
                max_list.append(max(cur_front, cur_back))
        max_dp[i] = max(max_list)

for _ in range(Q):
    q = int(input())
    print("%d %d" %(min_dp[q], max_dp[q]))