1563 개근상 파이썬으로 풀기

이 문제는 보자말자 dp로 풀어야겠다 라고 생각했었습니다.

2일까지만 할수 있는 결석, 1번만 할수 있는 지각과 출석을 만약 순열로 푼다면 엄청난 조건들이 생길것이라 판단해서 바로 기각

그 다음 생각한 것이 dp밖에 없다고 생각했기 때문입니다.

다만 이전 일자로부터 다음 일자를 어떤 방법으로 채울수 있을까 고민했었습니다.

처음 생각한 방법은

list를 3중으로 해서 [현재 일자][0 : 어제 지각, 결석 정보][1 : 이틀전 지각, 결석 정보]

리스트를 2개를 가지고

이틀전 지각, 결석 정보

하루전 지각, 결석 정보를 확인한 다음 이것으로 판단해야겠다고 생각했습니다.

그래서 boolean으로 값들을 정리하고 count하는 방법을 생각했는데요. 

문제는 각 경우의 수마다 dp 값들이 달라진다는 것!

 

그래서 [현재일자][지각 여부][결석 횟수] 이렇게 가져가면 깔금하게 해결되는것을 알게 되었습니다.

import sys
input = sys.stdin.readline
# 1563 개근상
# 2번이상 지각하거나 3번연속 결석하면 개근상을 받지 못한다.
# O : 출석, L : 지각, A : 결석
n = int(input())
dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n+1)] 
# 출석은 마음껏 할수 있고, 지각은 1번까지, 결석은 이전에 하지 않은 경우 0으로 변하고 최대 2까지 쌓을 수 있다.
# 저장할 값 날짜, 횟수, 총 개수
# 하지만 총 개수만큼 리스트를 만들게 되면 엄청난 메모리 이슈가 발생한다. 지각과 결석을 리스트로 만들어 내자
dp[1][0][0] = 1 # 출석을 한경우
dp[1][0][1] = 1 # 결석을 한경우
dp[1][1][0] = 1 # 지각을 한경우
maxValue = 1000000
for i in range(2, n+1):
  # 출석한다면
  dp[i][0][0] = sum(dp[i-1][0]) % maxValue
  # 출석 + 지각
  dp[i][1][0] = (sum(dp[i-1][1]) + sum(dp[i-1][0])) % maxValue
  # 결석한다면
  dp[i][0][1] = dp[i-1][0][0] % maxValue
  dp[i][0][2] = dp[i-1][0][1] % maxValue
  dp[i][1][1] = dp[i-1][1][0] % maxValue
  dp[i][1][2] = dp[i-1][1][1] % maxValue
print((sum(dp[n][0]) + sum(dp[n][1])) % maxValue)

 

그리고 최대값이 설정되어 있어서 곳곳에 maxValue의 나머지로 나눠주는 방법을 택했습니다.

 

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

1563번: 개근상