최댓값 대신 가능한 방법 수를 저장해요
앞 DP에서는 선택/미선택 중 큰 값을 골랐어요. 이번에는 서로 다른 방법을 모두 세요. 0번 칸에서 시작해 한 번에 1칸 또는 2칸 이동할 때, 이동 순서가 다르면 다른 방법이에요.
ways[i]를 ‘정확히 i칸 앞으로 가는 방법 수’로 정해요. i에 마지막으로 들어온 이동은 1칸 또는 2칸 중 하나예요. 두 종류는 마지막 이동이 달라 서로 겹치지 않으므로 방법 수를 더할 수 있어요.
아무것도 이동하지 않는 방법도 하나예요
| 목표 칸 | 방법 | 개수 |
|---|---|---|
| 0 | 아무 이동도 하지 않음 | 1 |
| 1 | 1 | 1 |
| 2 | 1+1, 2 | 2 |
| 3 | 1+1+1, 1+2, 2+1 | 3 |
2+1과 1+2는 순서가 다른 두 방법이에요. 목표 4로 끝나는 방법은 3까지 온 뒤 1칸 가는 방법과 2까지 온 뒤 2칸 가는 방법으로 나눠요. 따라서 개수는 얼마일까요? 3+2=5예요. 큰 답은 1,000,000,007로 나눈 나머지를 저장해 정수 범위를 관리해요.
직접 풀어봐요
0번 칸에서 n번 칸까지 한 번에 1칸 또는 2칸씩만 앞으로 이동해요. 정확히 도착하는 이동 순서의 개수를 1,000,000,007로 나눈 나머지로 반환해요. n=0이면 이동하지 않는 방법 하나라 1을 반환해요.
n은 0~1000이에요. 실행용 입력은 n 한 개, 출력은 반환값이에요. 하네스가 입출력을 처리해요.
예시 1: n=4 → 5. 마지막 이동이 1인 세 방법과 2인 두 방법을 합해요.
예시 2: n=5 → 8. 4칸까지의 다섯 방법과 3칸까지의 세 방법을 이어 써요.
예시 입력
4
예상 결과
5
예시 입력
5
예상 결과
8
핵심 개념
dp-1d: 마지막 이동이 다른 경우의 수를 더해요.