박상어 블로그

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 평범한 dfs 문제지만, 문제에 어떻게 접근하냐에 따라 시간초과가 나올수도 있는 문제입니다. 문제에선 1, 5, 10, 50 > 4개의 수만 사용가능합니다. XXXV / IXI 같은 한 문자가 여러 개 들어간 문자열도 만들 수 있기에 dfs 구현 시 중복 방문도 가능하단 것을 확인할 수 있습니다. 그럼 이제 dfs를 구현할 두가지 방법이 있습니다. 1. 각 배열 요소를 저장한 뒤 조건이 충족되면 계산 2. dfs를 진행하면서 동시에 덧셈을 진행 1번같은 경우는 dfs에 대한 기본적인 개념을 알..