[BOJ]16922번: 로마 숫자 만들기

 

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

---

BFS 문제입니다.

 

매 깊이 마다 1,5,10,50을 더해봐서

 

X개의 숫자의 합으로 Y를 만든 적이 있는지 계속 저장하면서

 

N개를 모두 합쳤을 때의 값을 set에 저장해주었습니다.

 

상태를 탐색하는 방법은 DFS도 가능하겠지만 아마 재구 깊이를 20까지 탐색 하면 터지지 않을까 싶네요.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16922.cc