[백준] 1563 개근상

문제 링크

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

사용 알고리즘

• DP

풀이

여러 방법으로 시도하다 도저히 풀리지 않아 다른 사람의 풀이를 보고 푼 문제이다.

나는 출석, 지각, 결석에 따른 경우의 수를 저장하는 배열을 사용하려 했지만 구현 시 현재 출석했을 때 결석의 수를 초기화할 수 없기 때문에 잘못된 방식으로 접근했다.

 

이 문제를 해결하기 위해 만들어야 할 DP 배열은 i번째 날에 지각, 결석한 횟수에 따른 경우의 수를 저장하는 배열이다.

▶︎ `dp[학기의 날짜 수(= n + 1)][가능한 지각 횟수(= 2)][가능한 결석 횟수(= 3)]`

 

위와 같은 DP 배열을 만들면 현재 날짜의 지각, 결석 횟수에 따른 경우의 수를 저장할 수 있다.

현재 날짜의 지각, 결석 횟수에 따라 아래와 같은 경우가 나올 수 있다.

• 지각 0 & 결석 0
• 지각 0 & 결석 1
• 지각 0 & 결석 2
• 지각 1 & 결석 0
• 지각 1 & 결석 1
• 지각 1 & 결석 2

지각 0 & 결석 0

결석은 현재 날짜에 출석을 하면 초기화된다.

지각을 한번도 하지 않았고 결석도 한번도 하지 않았다면 오늘 출석을 했다는 뜻이다.

 

따라서, 지각을 한번도 하지 않았고 결석도 한번도 하지 않았다면 i - 1번째 날짜의 지각을 하지 않았을 경우의 수를 모두 더해주면 된다.

▶︎ `dp[i][0][0] = sum(dp[i - 1][0])`

 

지각 0 & 결석 1

현재 날짜에 결석을 한 경우이다.

 

지각을 한번도 하지 않았고 현재 날짜에 결석을 했다면 전날 지각을 한번도 하지 않았고 출석한 경우의 수를 그대로 가져온다.

▶︎ `dp[i][0][1] = dp[i - 1][0][0]`

 

지각 0 & 결석 2

두번 연속으로 결석을 한 경우이다.

 

지각을 한번도 하지 않았고 전일 결석 & 현재 날짜에 결석을 했다면 전날 지각을 한번도 하지 않았고 결석한 경우의 수를 그대로 가져온다.

▶︎ `dp[i][0][2] = dp[i - 1][0][1]`

 

지각 1 & 결석 0

현재까지 한 번 지각했고 결석을 하지 않은 경우이다.

 

마찬가지로 결석은 현재 날짜에 출석을 하면 초기화되기 때문에 0번 지각했을 경우의 모든 경우의 수와 1번 지각했을 경우의 모든 경우의 수를 더해주면 된다.

▶︎ `dp[i][1][0] = sum(dp[i - 1][0]) + sum(dp[i - 1][1]`

 

지각 1 & 결석 1, 지각 1 & 결석 2

이 경우에는 지각 0 & 결석 1, 지각 0 & 결석 2와 동일하게 이전까지 1번 지각하고 각각 0, 1번 결석한 경우를 그대로 가져온다.

▶︎ `dp[i][1][1], dp[i][i][2] = dp[i - 1][1][0], dp[i - 1][1][1]`

 

최종적으로 모든 경우의 수를 구하기 위해선 0번 지각했을 때 경우의 수의 합과 1번 지각했을 때 경우의 수의 합을 더해주면 된다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

MOD = 1000000

n = int(input())
dp = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]
dp[1][0][0], dp[1][1][0], dp[1][0][1] = 1, 1, 1

for i in range(2, n + 1):
    dp[i][0][0] = sum(dp[i - 1][0]) % MOD
    dp[i][0][1] = dp[i - 1][0][0] % MOD
    dp[i][0][2] = dp[i - 1][0][1] % MOD
    dp[i][1][0] = sum(dp[i - 1][0]) % MOD + sum(dp[i - 1][1]) % MOD
    dp[i][1][1] = dp[i - 1][1][0] % MOD
    dp[i][1][2] = dp[i - 1][1][1] % MOD

print((sum(dp[-1][0]) + sum(dp[-1][1])) % MOD)