백준 1904 : 01타일 (파이썬)

ㅓ간단한 DP 문제였다.

예전에 이것과 비슷한 문제 (피보나치수열로 진행되는 문제) 를 풀어 본 경험이 있었는데,

그것과 매우 비슷하다는 것을 금방 깨달았다.

 

N = int(input())
dp = [0] * (N + 1)
dp[1] = 1
if N > 1:
    dp[2] = 2
    for i in range(3, N + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
print(dp[N])

 

다만 15746 으로 나누는 부분에서 메모리 초과 한 번, 인덱스 범위 정해 줄 때 오류 한 번 해서 총 두 번 오답이 나왔는데

인덱스 부분은 오류를 금방 찾았지만 15746 으로 나누는 부분을 늦게 떠올렸다.

 

신기하면서 이해가 잘 되지 않았던 점은 15746 으로 나눈 나머지를 dp 에 적용시켜서 더해도 정답이 틀리지 않는다는 것이다. 막연히 분배법칙이 통하지 않을까 해서 풀긴 했지만 거의 감으로 푼 것이라 조금 마음에 걸리기는 한다.

 

그래서 찾아보았는데 15746으로 나누는 것에 대한 이유로 나머지 연산 분배법칙이라는 것이 있다고 한다.

 

나머지(Modulo) 연산 분배법칙

 

분배법칙 비슷하게 뭔가 적용되지 않을까 하는 감이 맞았던 것이었다.