0912_algorithm_16922_로마숫자만들기

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

초기 구상과정

1. 재귀호출 DFS로 풀기
2. case 나누기 I V X L 4가지
   {'I': 1, 'V': 5, 'X': 10, 'L': 50}
   ['I', 'V', 'X', 'L']
3. 종결조건 : step == N
4. 중복처리(순서 생각 안함)
   예제 2 > IV, VI : 6 / VX, XV : 15 등등

초기 코드

def dfs(step, N):
    global result
    if step == N:
        result.append(sum(tmp))
    else:
        for i in range(4):
            tmp.append(rom_nums[i])
            dfs(step + 1, N)
            tmp.pop()

N = int(input())
rom_nums = [1, 5, 10, 50]
result = []
tmp = []
dfs(0, N)
ans = len(set(result))
print(ans)

간단히 생각해서 '중복은 set으로 처리하면 시간이 그리 오래 걸리지 않겠지'라고 생각해서 풀었는데 시간초과로 fail.. 이 때부터 시간을 줄이려고 방법을 찾기 시작했다. append(), set(), sum() 등등의 내장함수들의 시간복잡도를 찾아보기도 하고 문제점이 무엇일까 고민을 했다.

두번째 제출

def dfs(step, N):
    global result
    if step == N:
        if sum(tmp) not in result:
            result.append(sum(tmp))
    else:
        for i in range(4):
            tmp.append(rom_nums[i])
            dfs(step + 1, N)
            tmp.pop()

N = int(input())
rom_nums = [1, 5, 10, 50]
result = []
tmp = []
dfs(0, N)
ans = len(result)
print(ans)

먼저 모든 결과들을 중복을 제외하지 않고 result에 다 넣고 문제를 푸려고 하는 부분이 문제일 것으로 예상하고 중복을 제외하며 저장하기 위해서 코드를 바꿔 봤지만 똑같은 이슈가 발생해서 fail

세번째 제출

def dfs(step, N, summation):
    global result
    if step == N:
        result[summation] = 1
        return
    else:
        for i in range(4):
            dfs(step + 1, N, summation + rom_nums[i])


N = int(input())
rom_nums = [1, 5, 10, 50]
result = [0] * (50 * 20 + 1)
dfs(0, N, 0)
ans = len([x for x in result if x != 0])
print(ans)

append()가 문제일까 생각해봐서 백준 질문게시판에 있는 힌트를 받고 append()를 사용하지 않고 메모리를 더 써서 result를 1001개의 list로 구성하고 합을 인덱스로 사용하여 답을 구하는 방법을 써봤지만 결국 또 시간초과로 틀렸다.

최종 코드

def dfs(step, N, summation, n):
    global result
    if step == N:
        result[summation] = 1
        return
    else:
        for i in range(n, 4):
            dfs(step + 1, N, summation + rom_nums[i], i)

N = int(input())
rom_nums = [1, 5, 10, 50]
result = [0] * (50 * 20 + 1)
dfs(0, N, 0, 0)
ans = sum(result)
# ans = len(result)
print(ans)

결국 답을 찾았는데 내장함수들의 시간복잡도 보다 검색하는 케이스 수를 줄이는 것이 관건이었다. backtracking이라고 하면 기본적으로 구동하는 for문에서 적용하는 것이 아니라 if elif else문에서 따로 처리한다는 고정관념이 있던 것이 큰 문제였다. 굳이 중복을 따로 위에서 처리하지 않고 for문에서 그냥 바로 처리하니 훨씬 더 간단하고 빠른 backtracking이 되었다. 단순히 앞선 케이스들을 제외하기 위해서 range를 n부터 3까지 확인하도록 만들어 주는 것이 중복된 케이스들을 제외하는 확실한 방법이 되었다.

느낀점

'backtracking에서 방법은 단 하나로 고정되어있지 않다.'라는 것을 함부로 배제를 하고 있었다는 것이 가장 큰 오류였다. 코딩을 하면서 나의 방법만이 맞다는 것은 절대 금물이라는 사실을 알고 있었지만 유연한 사고에서 더 나은 코드를 작성할 수 있다는 점이 가장 큰 교훈이었다.