[BOJ] 3687 - 성냥개비 (Python)

 

 

아이디어

 

문자열의 접두사와 접미사가 일치하면서 문자열 중간에 등장하는 가장 긴 부분 문자열을 찾는다.

 

 

풀이

 

숫자 0~9는 성냥개비 2~7개로 모두 표현할 수 있다.

리스트 M에 인덱스만큼의 성냥개비로 만들 수 있는 가장 작은 수를 저장한다.

 

리스트 dp에 인덱스 7까지는 M과 같은 값들을 저장하고, 인덱스 8에는 10을 저장하여 for문이 9부터 시작하도록 한다.

인덱스 8을 이후 for문에서 접근하면 dp[8-7]로 dp[1]을 가리켜 값이 잘못 저장되기 때문이다.

성냥개비 2~7개마다 자릿수가 하나씩 늘어나므로 이전 수에서 자릿수를 늘려 만들 수 있는 가장 작은 수를 저장해 나간다.

 

성냥개비로 가장 큰 수를 만들기 위해서는 가능한 적은 성냥개비를 사용하여 자릿수를 크게 만드는 것이므로,

성냥개비 2개로 만들 수 있는 1을 최대한 포함하고, 성냥개비가 홀수인 경우 3개로 만들 수 있는 7이 맨 앞에 오도록 한다.

 

import sys

input = sys.stdin.readline

def solution():
    dp = [0]*101
    M = [0, 0, 1, 7, 4, 2, 0, 8]
    dp[:9] = M+[10]
    dp[6] = 6
    for i in range(9, 101):
        dp[i] = dp[i-2]*10+M[2]
        for j in range(3, 8):
            dp[i] = min(dp[i], dp[i-j]*10+M[j])
    T = int(input())
    for t in range(T):
        n = int(input())
        max_val = '7'+'1'*((n-3)//2) if n%2 else '1'*(n//2)
        print(dp[n], max_val)

solution()