[BOJ] Q3687 성냥개비

[BOJ] Q3687 성냥개비

Question

Language: Python

Difficulty: Gold 2

무작정 모든 숫자를 다 구하려고 하면 시간 초과나는 문제이다.

우선 쉬운 최대값 부터 살펴보자, 최대값은 항상 자리수가 커지면 숫자는 자연스럽게 커진다. 그래서, 획수가 가장 작은 1을 이용해서 자리를 최대한 키우면서, 만약 성냥개비 개수가 1의 획수의 배수가 되지 않을때는 그 다음 적은 획수의 숫자를 맨 앞에 붙인다.

예시,

1. 성냥개비 개수가 8개이다. 1의 획수가 2이므로, 8은 2로 나눠떨어진다. 그러므로 1111이 최대값이다.

2. 성냥개비의 개수가 9개이다? 9는 2로 나눠 떨어지지 않으므로, 3+2+2+2의 조합으로, 7111이 최대값이다.

이렇게 최대값은 2가지 경우만 생각해서 만들 수 있다.

다음은, 최소값 이다

최소값은 최대한 자리수를 낮춰야하며, 앞에 오는 숫자가 작을 수록 좋다

우선, dp[2]=1,dp[3]=7,dp[4]=4,dp[5]=2,dp[6]=6,dp[7]=8 는 이미 구해진 값이므로 이를 이용하자 획수가 8인 수를 구하기 위해서는 위의 숫자를 조합해서 최소의 숫자를 구해야한다.(단, 0은 뒤에 붙일 수 있다.)

1. 만약, 앞에 획수가 2인 1이 오면 뒤에는 획수가 6인 6이 올 수 있는데(이때 획수가 6인 값들이 뒤에 오면 0이 오는 게 가장 작은 값이 된다). 이렇게 해서 만들어지는 값이 10
2. 만약, 앞에 획수가 3인 7이 오면 뒤에는 획수가 5인 2이 올 수 있는데 이러면 값이 72
3. 만약, 앞에 획수가 4인 4이 오면 뒤에는 획수가 4인 4이 올 수 있는데 이러면 값이 44
4. 만약, 앞에 획수가 5인 2이 오면 뒤에는 획수가 3인 7이 올 수 있는데 이러면 값이 27
5. 만약, 앞에 획수가 6인 6이 오면 뒤에는 획수가 2인 1이 올 수 있는데 이러면 값이 61 이중에서 최소값은 10이다

즉, 매 값마다, dp[i]=min(dp[i-j]+dp[j])[2<=j<8] 해당 점화식을 통해 값을 구하는 것이다.

Solution

from math import inf

def setMinNum():
    dp[2]=1
    dp[3]=7
    dp[4]=4
    dp[5]=2
    dp[6]=6
    dp[7]=8
    
    for i in range(8,101):
        for j in range(2,8):
            if j!=6:
                temp=dp[i-j]*10+dp[j]
            else:
                temp=dp[i-j]*10
            dp[i]=min(dp[i],temp)
    return dp

def solution(n):
    max_num=0
    if n %2==0:
        max_num=int("1"*(n//2))
    else:
        max_num=int("7"+"1"*(n//2 -1))
    
    print(dp[n],max_num)

if __name__ == "__main__":
    testcases=int(input())
    dp=[inf]*101
    dp=setMinNum()
    for _ in range(testcases):
        n=int(input())
        solution(n)