문제 소개
두 개의 정수 n과 k가 주어집니다. n은 앞으로 진행할 게임의 총 횟수를 의미하고, k는 허용되는 최대 연속 승리 횟수를 나타냅니다. 목표는 n번의 게임에서 연속 승리 횟수가 k회 이하가 되도록 승(W)과 패(L)를 배치하는 서로 다른 경우의 수를 구하는 것입니다. 답이 매우 커질 수 있으므로 결과는 10⁹ + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 n = 3, k = 2인 경우를 살펴보겠습니다. 이때 정답은 7입니다. 전체 2³ = 8가지 조합 중 연속 3승인 "WWW" 하나만 조건을 위반하므로, 나머지 7가지가 모두 유효한 경우입니다.
["LLL", "WLL", "LWL", "LLW", "WWL", "LWW", "WLW"]
여기서 W는 승리(Win), L은 패배(Lose)를 의미합니다.
풀이 아이디어: 동적 프로그래밍(DP)
각 게임마다 승리 또는 패배라는 두 가지 선택지가 있으며, 다음 게임에서의 제약은 오직 "현재까지의 연속 승리 횟수"에만 의존합니다. 이러한 구조는 상태 (게임 번호 i, 연속 승리 횟수 K)를 기준으로 재귀적으로 해결할 수 있는 대표적인 동적 프로그래밍 문제입니다.
- 모듈러 값 설정: m = 10⁹ + 7로 정의하여 값이 커지는 것을 방지합니다.
- DP 함수 정의: dp(i, K)는 i번째 게임부터 끝까지 진행할 때 가능한 경우의 수를 반환합니다.
- 가지치기: K > k가 되면 이미 조건을 위반한 경로이므로 0을 반환합니다.
- 종료 조건: i == n이면 모든 게임을 마친 유효한 경로이므로 1을 반환합니다.
- 점화식: dp(i, K) = dp(i+1, 0) + dp(i+1, K+1) — 이번 게임에서 패배하면 연속 승리가 초기화되고, 승리하면 연속 승리가 1 증가합니다.
- 최종 답: dp(0, 0) % m을 반환합니다.
파이썬 구현 코드
def solve(n, k):
m = 10**9 + 7 # 결과를 나눌 모듈러 값
def dp(i, K):
# 연속 승리가 한도를 초과하면 유효하지 않은 경로
if K > k:
return 0
# 모든 게임을 완료하면 유효한 경우 1가지로 카운트
if i == n:
return 1
# 패배하는 경우 + 승리하는 경우
return (dp(i + 1, 0) + dp(i + 1, K + 1)) % m
return dp(0, 0) % m
n = 3
k = 2
print(solve(n, k))실행 결과
7성능 개선: 메모이제이션 적용
위 구현은 동일한 상태가 반복 호출되어 시간 복잡도가 O(2ⁿ)로 지수급입니다. 파이썬의 functools.lru_cache 데코레이터를 사용하면 각 상태 (i, K)를 한 번만 계산하므로 성능이 크게 향상됩니다.
from functools import lru_cache
def solve(n, k):
m = 10**9 + 7
@lru_cache(maxsize=None)
def dp(i, K):
if K > k:
return 0
if i == n:
return 1
return (dp(i + 1, 0) + dp(i + 1, K + 1)) % m
return dp(0, 0)
print(solve(3, 2)) # 출력: 7
print(solve(4, 2)) # 출력: 13복잡도 분석
- 시간 복잡도: 메모이제이션 적용 시 O(n × k) — 상태의 수가 게임 번호 n과 연속 승리 횟수(k+1가지)의 곱으로 제한됩니다.
- 공간 복잡도: O(n × k) — 캐시 저장 공간과 재귀 호출 스택이 필요합니다.
이처럼 동적 프로그래밍을 활용하면 지수적인 탐색 공간을 다항 시간으로 줄일 수 있으며, n이 수천 이상으로 커지더라도 안정적으로 정답을 구할 수 있습니다.