길이가 n인 리스트의 인덱스 0 위치에 서 있다고 가정해 보겠습니다. 각 단계에서 우리는 오른쪽으로 한 칸 이동하거나, 왼쪽으로 한 칸 이동하거나(리스트의 경계를 벗어나지 않는 범위에서), 또는 제자리에 그대로 머무를 수 있습니다. 이때 정확히 k번의 이동을 수행한 뒤 다시 인덱스 0으로 돌아올 수 있는 서로 다른 이동 경로가 총 몇 가지인지 구해야 합니다. 답이 매우 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환합니다.
문제 예시
예를 들어 n = 7, k = 4가 입력으로 주어지면 출력은 9가 됩니다. 가능한 이동 순서는 다음과 같습니다.
- [오른쪽, 오른쪽, 왼쪽, 왼쪽]
- [오른쪽, 왼쪽, 오른쪽, 왼쪽]
- [대기, 대기, 대기, 대기]
- [오른쪽, 왼쪽, 대기, 대기]
- [대기, 대기, 오른쪽, 왼쪽]
- [오른쪽, 대기, 대기, 왼쪽]
- [오른쪽, 대기, 왼쪽, 대기]
- [대기, 오른쪽, 왼쪽, 대기]
- [대기, 오른쪽, 대기, 왼쪽]
풀이 접근 방법
이 문제는 재귀적 동적 계획법(DP)으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
- m := 10^9 + 7 (모듈로 값)
- N := 리스트의 길이
- 현재 위치 i와 남은 이동 횟수 jumps를 받는 dp() 함수를 정의합니다.
- jumps가 0이라면, i가 0일 때 1(참), 아니면 0(거짓)을 반환합니다.
- count := dp(i, jumps - 1) → 제자리에 머무는 경우
- i >= 0이면 count에 dp(i + 1, jumps - 1)을 더합니다 → 오른쪽으로 이동하는 경우
- i <= N - 1이면 count에 dp(i - 1, jumps - 1)을 더합니다 → 왼쪽으로 이동하는 경우
- count를 반환합니다.
- 메인에서는 최종적으로 dp(0, n) mod m을 반환합니다.
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
구현 예제
class Solution: def solve(self, length, n): MOD = 10 ** 9 + 7 N = length def dp(i, jumps): if jumps == 0: return +(i == 0) count = dp(i, jumps - 1) if i >= 0: count += dp(i + 1, jumps - 1) if i <= N - 1: count += dp(i - 1, jumps - 1) return count return dp(0, n) % MOD ob = Solution() n = 7 k = 4 print(ob.solve(n, k))
입력
7, 4
출력
9
성능 개선: 메모이제이션 적용하기
위 재귀 구현은 동일한 상태 (i, jumps)를 여러 번 반복해서 계산하므로, k가 커지면 실행 시간이 기하급수적으로 늘어날 수 있습니다. 파이썬의 functools.lru_cache 데코레이터를 활용해 이미 계산한 상태를 캐싱하면 중복 연산을 제거하고 시간 복잡도를 O(N × k) 수준으로 크게 줄일 수 있습니다.
from functools import lru_cache class Solution: def solve(self, length, n): MOD = 10 ** 9 + 7 N = length @lru_cache(maxsize=None) def dp(i, jumps): if jumps == 0: return +(i == 0) count = dp(i, jumps - 1) if i >= 0: count += dp(i + 1, jumps - 1) if i <= N - 1: count += dp(i - 1, jumps - 1) return count return dp(0, n) % MOD
이처럼 재귀 DP의 기본 구조를 이해하고 메모이제이션을 더하면, 같은 로직으로 훨씬 큰 입력도 효율적으로 처리할 수 있습니다.