[Python] 1563번 개근상

 

 

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

1563번: 개근상

---

 

23/03/09

 

 

3차원 DP문제로, 상태를 정의하기만 하면 점화식을 구성하는 것은 그렇게 어렵지 않아서, 쉽게 풀 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

문제를 자세히 보면, 개근상을 받을 수 없는 경우를 주목해야 할 필요가 있다.

 

개근상을 받을 수 없는 경우는 $N$일 중에서 지각이 $2$회 이상이거나, 결석이 연속 $3$회 이상이면 개근상을 받을 수 없다.

 

반대로 말하면, $N$일 중에서 지각이 $1$회 이하이거나, 결석이 연속 $2$회 이하이면 개근상을 받을 수 있다는 것이다.

 

 

점화식을 구성할 때, 영향을 미치는 요인은 몇 일 나왔는지, 그 중 지각이 몇 번인지, 지금까지 결석을 연속으로 몇 번 했는지가 영향을 미친다는 사실을 알 수 있다.

 

이 사실을 통해 $\mathrm{DP}$식을 다음과 같이 구성할 수 있다.

 

$\mathrm{DP}[n][i][j]$ $=$ $n$일 동안 지각을 총 $i$번 하고, 연속으로 결석한 횟수가 $j$번 일 때의 상태

 

이렇게 상태를 정의하면 총 6개의 상태가 나올 수 있다는 사실을 우리는 잘 안다.

 

$\mathrm{DP}[N][0][0]$ $=$ $N$일동안 지각을 한번도 안하고 연속 결석 $0$번일때
$\mathrm{DP}[N][0][1]$ $=$ $N$일동안 지각을 한번도 안하고 연속 결석 $1$번일때
$\mathrm{DP}[N][0][2]$ $=$ $N$일동안 지각을 한번도 안하고 연속 결석 $2$번일때
$\mathrm{DP}[N][1][0]$ $=$ $N$일동안 지각 한번 하고 연속 결석 $0$번일때
$\mathrm{DP}[N][1][1]$ $=$ $N$일동안 지각 한번 하고 연속 결석 $1$번일때
$\mathrm{DP}[N][1][2]$ $=$ $N$일동안 지각 한번 하고 연속 결석 $2$번일때

 

여기서 확인할 수 있는 각각의 상태 전이는 다음과 같다.

 

$N+1$일 동안 지각 한번도 안하고 연속 결석 $0$번인 상태는 $N$일 동안 지각 한번도 안하고 연속 결석 $0$번, $1$번, $2$번인 상태에서 각각 출석하면 되므로, 아래와 같은 식이 나온다.

$$\mathrm{DP}[N+1][0][0] = \mathrm{DP}[N][0][0] + \mathrm{DP}[N][0][1] + \mathrm{DP}[N][0][2]$$

 

$N+1$일 동안 지각 한번도 안하고 연속 결석 $1$번인 상태는 $N$일 동안 지각 한번도 안하고 연속 결석 $0$번인 상태에서 결석하면 되므로, 아래와 같은 식이 나온다.

 

$$\mathrm{DP}[N+1][0][1] = \mathrm{DP}[N][0][0]$$

$N+1$일 동안 지각 한번도 안하고 연속 결석 $2$번인 상태는 $N$일 동안 지각 한번도 안하고 연속 결석 $1$번인 상태에서 결석하면 되므로, 아래와 같은 식이 나온다.

$$\mathrm{DP}[N+1][0][2] = \mathrm{DP}[N][0][1]$$


$N+1$일 동안 지각 한번 하고 연속 결석 $0$번인 상태는 $N$일 동안 지각 한번 한 상태에서 출석 하거나, $N$일 동안 지각 한번도 하지 않은 상태에서 지각하면 되므로, 아래와 같은 식이 나온다. 

$$\mathrm{DP}[N+1][1][0] = (\mathrm{DP}[N][1][0] + \mathrm{DP}[N][1][1] + \mathrm{DP}[N][1][2] + \mathrm{DP}[N][0][0] + \mathrm{DP}[N][0][1] + \mathrm{DP}[N][0][2])$$

$N+1$일 동안 지각 한번 하고 연속 결석 $1$번인 상태가 되려면 $N$일 동안 지각 한번 하고 연속 결석 $0$번인 상태에서 결석을 하면 되므로, 아래와 같은 식이 나온다.

$$\mathrm{DP}[N+1][1][1] = \mathrm{DP}[N][1][0]$$

$N+1$일 동안 지각 한번 하고 연속 결석 $2$번인 상태가 되려면 $N$일 동안 지각 한번 하고 연속 결석 $1$번인 상태에서 결석 하면 되므로, 아래와 같은 식이 나온다.

$$\mathrm{DP}[N+1][1][2] = \mathrm{DP}[N][1][1]$$

 

이를 통해 주어진 제한 범위인 $N = 1000$까지의 $\mathrm{DP}$값을 미리 구해놓은 다음 출력하면 문제를 해결할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1563번 개근상
# 다이나믹 프로그래밍
'''
접근 방법:
DP[N][0][0] = N일동안 지각을 한번도 안하고 연속 결석 0번일때
DP[N][0][1] = N일동안 지각을 한번도 안하고 연속 결석 1번일때
DP[N][0][2] = N일동안 지각을 한번도 안하고 연속 결석 2번일때
DP[N][1][0] = N일동안 지각 한번 하고 연속 결석 0번일때
DP[N][1][1] = N일동안 지각 한번 하고 연속 결석 1번일때
DP[N][1][2] = N일동안 지각 한번 하고 연속 결석 2번일때

지각 한번도 안하고 연속 결석 0번인 상태는
지각 한번도 안하고 연속 결석 0번, 1번, 2번인 상태에서 각각 출석하면 되므로
DP[N+1][0][0] = DP[N][0][0] + DP[N][0][1] + DP[N][0][2]

지각 한번도 안하고 연속 결석 1번인 상태는
지각 한번도 안하고 연속 결석 0번인 상태에서 결석하면 되므로
DP[N+1][0][1] = DP[N][0][0]

지각 한번도 안하고 연속 결석 2번인 상태는
지각 한번도 안하고 연속 결석 1번인 상태에서 결석하면 되므로
DP[N+1][0][2] = DP[N][0][1]


연속 결석 2번, 또는 1번, 또는 0번인 상태에서 출석 하면 연속 결석 0번인 상태이고,
지각 한번도 안한 상태에서 지각 한번 하면 연속 결석이 초기화되고 넘어갈 수 있으므로
DP[N+1][1][0] = (DP[N][1][0] + DP[N][1][1] + DP[N][1][2]
                 DP[N][0][0] + DP[N][0][1] + DP[N][0][2])

지각 이미 한 상태에서 연속 결석 1번인 상태가 되려면 연속 결석 0번인 상태에서 결석을 하면 됨.
DP[N+1][1][1] = DP[N][1][0]

지각 이미 한 상태에서 연속 결석 2번인 상태가 되려면 연속 결석 1번인 상태에서 결석을 하면 됨.
DP[N+1][1][2] = DP[N][1][1]

이렇게 3차원 DP를 돌리면 된다.
'''
# 전처리 과정
MAX = 1000
MOD = 1000000
DP = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(MAX+1)]
DP[1][0][0], DP[1][0][1], DP[1][1][0] = 1, 1, 1
for N in range(1, MAX):
    DP[N+1][0][0] = (DP[N][0][0] + DP[N][0][1] + DP[N][0][2])%MOD
    DP[N+1][0][1] = DP[N][0][0]
    DP[N+1][0][2] = DP[N][0][1]
    DP[N+1][1][0] = (DP[N][1][0] + DP[N][1][1] + DP[N][1][2] +
                     DP[N][0][0] + DP[N][0][1] + DP[N][0][2])%MOD
    DP[N+1][1][1] = DP[N][1][0]
    DP[N+1][1][2] = DP[N][1][1]

n = int(input())
print((DP[n][1][0] + DP[n][1][1] + DP[n][1][2] + DP[n][0][0] + DP[n][0][1] + DP[n][0][2])%MOD)