문제
N일 동안 출석(O), 지각(L), 결석(A)를 기록할 때, 지각 1회 이하이고 연속 결석 2일 이하인 경우의 수를 구하라 (mod 1,000,000).
입력
N이 주어진다 (1 <= N <= 1000).
출력
개근상을 받을 수 있는 경우의 수를 1,000,000으로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 | 19 |
풀이
dp[i][j][k] = i일째, 지각 j회(0 or 1), 연속 결석 k일(0, 1, 2)인 경우의 수로 정의한다.
- 출석(O): 연속 결석 0으로 초기화, 지각 횟수 유지
- 지각(L): 연속 결석 0으로 초기화, 지각 횟수 1 증가 (이미 1이면 불가)
- 결석(A): 연속 결석 1 증가 (이미 2이면 불가)
- N일째 모든 유효 상태의 합을 출력한다
핵심 아이디어: 지각 횟수와 연속 결석 일수를 상태로 관리하면 전이가 O(1)이어서 전체 O(N)에 해결된다.
코드
MOD = 1000000
n = int(input())
dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)] # i, 지각, 결석
dp[1][0][0] = dp[1][1][0] = dp[1][0][1] = 1
for i in range(2, n + 1):
dp[i][0][0] = sum(dp[i - 1][0]) % MOD
dp[i][1][0] = sum(dp[i - 1][0]) % MOD + sum(dp[i - 1][1]) % MOD
dp[i][0][1] = dp[i - 1][0][0] % MOD
dp[i][1][1] = dp[i - 1][1][0] % MOD
dp[i][0][2] = dp[i - 1][0][1] % MOD
dp[i][1][2] = dp[i - 1][1][1] % MOD
print((sum(dp[n][0]) + sum(dp[n][1])) % MOD)복잡도
- 시간: O(N)
- 공간: O(N)