[ 16922 ] [ BFS ] 로마 숫자 만들기

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

16922번: 로마 숫자 만들기

 

---

풀이 과정

---

1. 사용 가능한 로마 숫자가 1, 5, 10, 50이며, N개의 숫자를 모두 사용했을 때 서로 다른 수의 개수를 출력
2. 따라서, 너비우선 탐색을 통해 만들 수 있는 서로 다른 수를 모두 구해준다.
   1. 중복이 있을 수 있으므로 SET 자료구조를 사용한다.
   2. 큐에 있는 각 숫자들을 하나씩 빼면서 1, 5, 10, 50을 더한 값을 중복 제거를 위해 임시로 set에 넣어준다.
   3. 큐가 비게 되면, set에 있는 값들을 큐에 넣어준다.
   4. 2-3 과정을 N번 반복해준 다음 최종적으로 set에 저장된 값의 개수를 출력시켜 준다.

---

소스 코드

---

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
numbers = [1, 5, 10, 50]

def solve():
    queue = deque([0])
    step = 0
    middle = set()
    answer = set()
    while True:
        x = queue.popleft()
        for num in numbers:
            middle.add(x+num)
        if not queue:
            step += 1
            if step == n:
                answer = middle
                break
            else:
                queue = deque(middle)
                middle = set()

    return len(answer)
    
print(solve())