[백준 1563 🥇] 개근상

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

1563번: 개근상

문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA 
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO 
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA 
LAOO LAOA LAAO

총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

문제 풀이

import sys
sys.setrecursionlimit(10**5)

n=int(sys.stdin.readline())

dp=[[[-1]*3 for _ in range(4)] for _ in range(n+1)]
def find_case(length, late, absent):
    global n
    if late>=2 or absent>=3:
        return 0
    if length==n:
        return 1
    if dp[length][late][absent]==-1:
        dp[length][late][absent]=(find_case(length+1, late, 0)
                +find_case(length+1, late+1, 0)
                +find_case(length+1, late, absent+1))%1000000
        return dp[length][late][absent]
    else:
        return dp[length][late][absent]

print(find_case(0,0,0))

• DP+DFS를 이용한 문제였다.
• 이런 유형이 여전히 어렵다 ㅠㅠ 갈 길이 멀다..!!
• DP를 이용해서 이전에 계산한 값들을 저장해두고 사용하지 않으면 메모리 초과가 발생한다.
• DP[n][late][absent] = num
  • N일째에 지각 late번, 연속 결석 absent번한 문자열의 경우의 수가 num개라는 뜻이다.
• find_case 함수를 사용해서 한 학기가 4일일 때의 모든 경우의 수를 구하는 흐름은 다음과 같다.
  • find_case(0,0,0)에서 시작해서 n일일 때 가능한 경우의 수를 DFS로 탐색하면서 구한다.
  • length : 현재까지 탐색한 날짜 수
  • late : 지각 일수
  • absent : 연속 결석 일수
  • dp[length][late][absent]가 아직 계산되지 않아 -1인 경우, 다음과 같이 find_case를 실행하고 이 함수들의 리턴값을 모두 더해서 dp[length][late][absent]에 저장한 뒤 리턴한다.  
    • 현재 상태에서 출석하는 경우의 수 find_case(length+1, late, 0)
    • 현재 상태에서 지각하는 경우의 수 find_case(length+1, late+1, 0)
    • 현재 상태에서 결석하는 경우의 수 find_case(length+1, late, absent+1)
    • (연속 결석 일수이므로 출석하거나 지각하는 경우 absent는 리셋된다.)
  • find_case(length, late, absent)에서 late>=2이거나 absent>=3이면 0을 반환하고, length가 n이면 1을 반환한다.
  • 두 경우 모두 아닐 경우 dp[length][late][absent]가 이미 계산되어 있어서 dp 배열의 초기화 값인 -1이 아니면 dp[length][late][absent]를 반환한다. (이러한 과정을 통해 이미 계산한 값을 다시 계산하지 않음으로써 시간 초과와 메모리 초과를 받지 않을 수 있다!)
  • dp[length][late][absent]==-1일 경우, dp 값을 계산한다.

n=4일 때 dp+dfs 과정