2193번 Python

이번에도 점화식을 먼저 찾기 위해 0이 마지막일 때, 1이 마지막일 때를 비교해보았다.

 

d[1][0] = 0
d[1][1] = 1

d[2][0] = 1
d[2][1] = 0

d[3][0] = 1
d[3][1] = 1

마지막 값이 0번째인 거부터 확인해보면 d[3][0] = d[1][0] + d[2][0]이라는 것을 확인할 수 있다.

 

d[i][j] = d[i-2][j] + d[i-1][j]

다음과 같은 점화식을 구해낼 수 있다.

 

import sys

n = int(sys.stdin.readline())
dp = [[0] * 2 for _ in range(n + 1)]
cnt = 0

for i in range(1, 3):
    dp[i][0] = cnt
    cnt += 1

cnt -= 1

for i in range(1, 3):
    dp[i][1] = cnt
    cnt -= 1

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

print(sum(dp[n]))

처음에는 이렇게 코드를 구성했는데 런타임 에러가 났다. 뒤늦게 확인해보니 n이 1인 경우에는 out of range가 발생했다.

 

import sys

n = int(sys.stdin.readline())
dp = [[0] * 2 for _ in range(n + 1)]
cnt = 0

if n >= 1:
    dp[1][0] = 0
    dp[1][1] = 1

if n >= 2:
    dp[2][0] = 1
    dp[2][1] = 0

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

print(sum(dp[n]))

분기문을 통해 1, 2일 때는 그냥 dp 리스트에 고정값으로 넣게 바꾸면서 정답이 될 수 있었다.

 

import sys

n = int(sys.stdin.readline())
dp = [0] * (n + 1)
dp[1] = 1

if (n > 1): dp[2] = 1

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

print(dp[n])

그런데 사실 이는 2차 배열로 구성할 이유가 전혀 없었다. 각 자릿수의 배열 합을 놓고 보면 결국 피보나치 수열 형태가 되어버리는 것이고 이는 dp의 기본 개념이기에 적용했을 때 바로 정답이 될 수 있었다.