문제
어느 보드 게임은 0번 칸부터 N번 칸까지 N+1 개의 칸이 일렬로 놓인 보드와 말 하나로 구성되어 있다. 처음에는 시작 지점인 0번 칸에 말을 두고, 말을 도착 지점인 N번 칸까지 옮기는 것이 게임의 목표이다.
말을 옮길 때는 다음 규칙을 따라야 한다. 말을 한 번 옮길 때 항상 1칸 또는 3칸 앞으로만 옮길 수 있으며, 보드 밖으로 말을 옮길 수는 없다.
해당 규칙에 따라서 시작 지점에서 도착 지점까지 말을 옮길 수 있는 방법의 개수를 출력하시오.
단, 값이 너무 커질 수 있으니 1,000,000,007로 나눈 나머지를 출력하시오.
입력
첫째 줄에 N이 주어진다.
- 1 ≤ N ≤ 100,000
import sys
input = sys.stdin.readline
n = int(input())
board = [0] * (n+3)
board[0] = board[1] = board[2] = 1
for i in range(3, n+1):
board[i] = (board[i-1]+board[i-3]) % 1000000007
print(board[n])1칸 또는 3칸을 움직일 수 있으니 1번 칸 ~ 2번 칸 까지 가는 방법은 각각 1개이다.
3번 칸부터는 직전 칸들의 방법을 이용하여 방법의 개수를 구할 수 있다.
예를 들어 N번 칸 까지 가기 위해서는 N - 1번 칸이나 N - 3번 칸에 있어야 한다.
따라서 N - 1번 칸까지 갔던 방법의 개수 + N - 3번 칸까지 갔던 방법의 개수를 계산하면 해결된다.
생각보다 간단한 문제임에도 처음엔 낯설어서 복잡하게만 생각했던 문제이다.
※출처
https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반
