[Python] 백준 1563번: 개근상

https://www.acmicpc.net/problem/1563

1563번: 개근상

1. 인덱스, 지각 개수, 연속된 결석 횟수로 배열을 만들었다.

2. 현재를 기준으로 지각 0, 결석 0 이면, i-1의 (지각 0 + 결석 0, 1, 2 + 출석)이 된다.(결석은 연속된 것으로 하므로 출석이 오면 초기화됨)

3. 마찬가지로 지각 1, 결석 0 이면 지각은 연속된 것이아니라 고정이므로, i-1의 (지각 0 + 결석 0, 1, 2 + 지각), (지각 1 + 결석 0, 1, 2, + 출석) 이 된다.

4. 지각 0, 결석 1 이면, i-1의 지각 0, 결석 0 + 결석

5. 지각 1, 결석 1 이면, i-1의 지각 1, 결석 0 + 결석

6. 지각 0, 결석 2 이면, i-1의 지각 0, 결석 1 + 결석

7. 지각 1, 결석 2 이면, i-1의 지각 1, 결석 1 + 결석

 

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)