[python 구름] 보드 게임

다이나믹 프로그래밍(DP)

📜 접근 방법

1. 처음부터 접근하되 1칸과 3칸 기준으로 확인을 하기 때문에 3미만의 숫자들은 1로 둔다(0부터 시작이고 0, 1, 2는 한칸으로 밖에 갈 수 없음)
2. 3번째부터 확인을 하는데 3번째에서 한칸 뒤, 3번째에서 3칸 뒤의 값들을 더해서 저장한다. (1칸으로 가는 방법과 3칸으로 가는 방법 두가지 중 가능한 갯수)
3. 주어진 n까지 반복한다.

 

❌ 실패 코드

 

✅ 정답 코드

import sys
input = sys.stdin.readline

# 문제에서 주어진 것
MOD = 10 ** 9 + 7

n = int(input())
dp = [0 for i in range(n + 1)]

# 0부터 2번째 위치는 무조건 한칸만 가능하기 때문에 초기값을 1로 둠
dp[0] = dp[1] = dp[2] = 1

for i in range(3, n + 1):
	# 점화식
	dp[i] = (dp[i - 1] + dp[i - 3]) % MOD
print(dp[n])

 

💡알게 된점

DP문제는 더 많이 풀어봐야겠다.