반응형
16922
-
BOJ) 로마 숫자 만들기알고리즘/백준 2020. 6. 26. 15:51
로마 숫자 만들기 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 풀이 Brute force 문제를 푼지 오래된 것 같아서 도전했다. n=20이기 때문에, 통과하려면 가지치기를 어떻게 해야하나 많은 고민을 해봤다. 질문 탭에도 게시글이 몇 개 없어서, 참고할 수도 없었다. 그래서, 처음 선택한 방법은 로마 숫자 1,5,10,50을 n만큼 2차원 배열을 만들어서 각 숫자가 0~n까지 반복하면 만들어지는 숫자를 저장했다. 이후에, 해당 숫자를 선택하면서 count를 i개 씩 줄여줬는데, 고작 해봐야 13 -> 14 정도까지만 구할 수 있었다. 어떻게 해야하나 고민하다가 Set에서 visit으로 바꿔주었다. 어차..