[Python] 백준 3687번: 박스 채우기

https://www.acmicpc.net/problem/3687

3687번: 성냥개비

1. 각 숫자마다 성냥의 갯수를 세서 배열에 넣어준다

2. 최댓값은 성냥이 적게들수록 자릿수가 높아지기 때문에 1과 7로만 이루어져있다.

3. 최솟값은 dp로 제일 최솟값을 구한다.

INF = 999999999999999999999999999999999999999999999999999

dy = [INF for _ in range(101)]
dy[2] = 1, dy[3] = 7, dy[4] = 4, dy[5] = 2, dy[6] = 0, dy[7] = 8


def go(x):
    if x <= 1:
        return dy[x]
    if dy[x] != INF:
        if x == 6:
            return 6
        return dy[x]
    else:
        for i in range(2, 8):
            tmp = go(x-i)
            dy[x] = min(dy[x], tmp*10 + dy[i])
    return dy[x]


n = int(input())

for _ in range(n):
    num = int(input())
    tmp = num
    maxx = 0
    minn = INF
    if num % 2 == 1:
        maxx = 7
        tmp -= 3
    while tmp:
        maxx = maxx * 10 + 1
        tmp -= 2

    print(go(num), maxx)