https://programmers.co.kr/learn/courses/30/lessons/12914
효진이는 한 번에 1칸이나 2칸을 뛸 수 있다. 효진이가 총 n개의 칸을 뛰어넘는 방법의 개수를 구하는 문제이다.
문제 접근하기
조합? 나누기? 어떤 방법을 써야할지 난감하지만 뛰어야 하는 칸의 개수를 하나씩 늘려가면서 써보면 의외로 간단하게 해결책이 발견된다.
뛰어야 하는 칸의 개수를 하나씩 늘려가며 경우의 수를 써보면 다음과 같다.
뛰어야 하는 칸이
- 1칸인 경우 -> (1칸) -> 1가지
- 2칸인 경우 -> (1칸, 1칸), (2칸) -> 2가지
- 3칸인 경우 -> (1칸, 1칸, 1칸), (2칸, 1칸), (1칸, 2칸) -> 3가지
- 4칸인 경우 -> (1칸, 1칸, 1칸, 1칸), (2칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 2칸) -> 5가지
- ...
1,2,3,5,7,... 피보나치 수열과 비슷하다! 이 규칙만 발견하고 풀어도 답을 낼 수 있다! 그래도 왜 이렇게 되는지 살펴보자.
점화식 세워보기
2칸까지는 직접 계산해주고,
- 1칸인 경우 -> (1칸)
- 2칸인 경우 -> (1칸,1칸), (2칸)
3칸인 경우는 다음 두 가지 경우로 나누어 생각할 수 있다.
- 1칸을 뛴 후에 + 2칸을 더 뛴다. -> (1칸) + (2칸)
- 2칸을 뛴 후에 + 1칸을 더 뛴다. -> (1칸,1칸), (2칸) + (1칸)
-> 3칸을 뛰는 방법: (1칸,2칸), (1칸,1칸,1칸), (2칸,1칸)
4칸인 경우
- 2칸을 뛴 후에 + 2칸을 더 뛴다. -> (1칸,1칸),(2칸) + (2칸)
- 3칸을 뛴 후에 + 1칸을 더 뛴다. -> (1칸,2칸), (1칸,1칸,1칸), (2칸,1칸) + (1칸)
-> 4칸을 뛰는 방법: (1칸,1칸,2칸), (2칸,2칸), (1칸,2칸,1칸), (1칸,1칸,1칸,1칸), (2칸,1칸)
n 칸인 경우
- n-2 칸을 뛴 후에 + 2칸을 더 뛴다.
- n-1 칸을 뛴 후에 + 1칸을 더 뛴다.
->n칸을 뛰는 방법 = (n-2칸을 뛰는 방법) + (n-1칸을 뛰는 방법)
코드 작성하기
def solution(n):
// n까지 뛰는 방법을 차례대로 저장하기 위한 배열을 선언한다.
// n=1인 경우 dp[1]에서 런타임 에러가 날 것이므로 필요한 배열보다 1칸 더 선언해 줬다.
dp = [0] * (n+1)
// 2칸까지는 직접 계산한 값을 미리 넣어준다.
dp[0] = 1
dp[1] = 2
//dp 을 차례로 채워넣는다.
for i in range(2,n):
dp[i] = dp[i-2] + dp[i-1]
// 정답은 실제 개수를 1234567로 나눈 나머지 값이므로
return dp[n-1] % 1234567