[백준] 20500번-(Python 파이썬) - DP

문제링크 : https://www.acmicpc.net/problem/20500

이번 문제는 1과 5로 이루어진 n자리의 수 중에서 15의 배수를 구하는 문제이다.
문제를 보자마자 점화식을 찾아낸 뒤 dp 테이블을 활용하여 구하기 위해 규칙을 찾기 시작했다.
4자리 수 까지 노트에 적어가며 규칙을 찾아봤었는데 정답은 나머지에 있었다.
맨 마지막 수가 1인 수는 당연히 15로 나누어지지 않으니 버리고, 마지막 수가 5이면서 15로 나누었을 때
나머지가 5인 경우와 10인경우 그리고 나누어떨어지는 경우 3가지로 나눌 수 있었다.
그렇게 노트에 써가며 규칙을 찾아간 결과 알아낸건 현재 자리수에서 나머지가 0, 5, 10인 수의 개수는 그전 자리수에서 나머지가 다른 수의 개수들의 합과 같다는 결론을 내리게 되었다.

dp[i][j]에서 j를 나머지 0, 5, 10라고 할 때
dp[i][0] = dp[i-1][1] + dp[i-1][2]
dp[i][1] = dp[i-1][0] + dp[i-1][2]
dp[i][2] = dp[i-1][0] + dp[i-1][1]

라는 간단한 점화식을 얻을 수 있다.

나머지가 0, 5, 10일 때에 따라 나누어 구한 풀이

n = int(input())

dp = [[0 for _ in range(3)] for _ in range(n + 1)]
dp[1][1] = 1

for i in range(2, n + 1):
    dp[i][0] = dp[i-1][1] + dp[i-1][2]
    dp[i][1] = dp[i-1][0] + dp[i-1][2]
    dp[i][2] = dp[i-1][0] + dp[i-1][1]

print(dp[n][0] % 1000000007)

제출 후 다른 분들의 코드를 보며 더 간단한 풀이를 찾다가
알게 된 풀이이다. 자리수가 짝수일 때와 홀수일 때에 개수에 규칙이 있을거라곤 상상도 못했는데
코드를 보고 노트를 보며 충격을 받았다.. 눈앞에 가까운길을 두고 먼길을 돌아간 기분이랄까..

i가 짝수일 때
dp[i] = (dp[i-1] 2) + 1
i가 홀수일 때
dp[i] = (dp[i-1] 2) - 1

자리수에 따라 나누어 푼 풀이

n = int(input())
dp = [0] * (n + 1)

for i in range(2, n + 1):
    if i % 2 == 0:
        dp[i] = (dp[i-1] * 2 + 1) % 1000000007
    else:
        dp[i] = (dp[i-1] * 2 - 1) % 1000000007
print(dp[n])