[ 3687 ] [ DP, BFS ] 성냥개비

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

3687번: 성냥개비

---

풀이 과정

---

1. 가장 큰 수를 만들려면 1, 7만으로 최대한 자리수를 늘리기만 하면 된다. (각각 2개, 3개이며 나머지는 4개 이상이므로 1 두개 넣는것보다 작음)

   • 성냥개비 개수가 홀수라면 맨앞에 7을 넣어주고 나머지는 1, 짝수라면 전체 1만으로 구성

2. BFS를 사용하여 DP 테이블을 채워준다.

   • 최대 100개의 성냥개비를 사용 가능하므로 100개까지 진행
   • DP[i]는 i개의 성냥개비로 만들 수 있는 수의 최솟값
   • 큐에 들어가는 형식은 [성냥개비 수, 만들어진 수]
   • 맨 앞자리는 0이 들어갈 수 없으므로, 초기 큐에는 1~9까지만 넣어준다.
   • 매 단계 큐에 넣을때마다 뒤에 09를 붙여주고, 09를 만드는데 필요한 성냥 수를 더해서 넘겨준다.
     • 성냥 수가 100개를 넘어가면 안됨.
   • 큐에서 빼낼 때, 만들어진 수가 기존 수보다 작을때만 뒤에 붙여주는 과정 진행

3. 최솟값, 최댓값 형식으로 출력시켜주면 된다.

• 최솟값이 굉장히 큰 수가 나올 수 있으므로 초기 값 설정을 잘 해주어야 함. 초깃값을 10e9로 했다가 처음엔 틀렸는데, sys.maxsize로 바꾸어주니 정답이 나옴.

---

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

INT_MAX = int(sys.maxsize)

dp_max = [0] * 101
dp_min = [INT_MAX] * 101

count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
initial = [[value, idx] for idx, value in enumerate(count)][1:]

queue = deque(initial)

while queue:
    cnt, make = queue.popleft()
    dp_min[cnt] = min(dp_min[cnt], make)
    if dp_min[cnt] != make:
        continue
    for i in range(10):
        if cnt + count[i] <= 100:
            queue.append([cnt + count[i], int(str(make)+str(i))])

for _ in range(T):
    p = int(sys.stdin.readline().rstrip())
    max_string = ''
    if p % 2 == 1:
        max_string = '7' + '1' * ((p-3) // 2)
    else:
        max_string = '1' * (p // 2)
    print(dp_min[p], max_string)