[백준/BOJ] gold4 - 1563번 개근상 (Python)

▶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으로 나눈 나머지를 출력한다.

 

▶예제

 

▶풀이

d는 날짜, l은 지각, a는 결석으로 두었고, dp는 3차원으로 해서 풀었다.

 

dp랑 dfs를 동시에 푸는 문제였다.

l은 누적 2번이니까 dfs 돌릴 때 +1해 주면 되고,

a는 연속 3번이니까 dfs 돌릴때 0으로 하거나 a+1 이렇게만 해주면 된다.

 

그래서 l이 2거나, a가 3이면 0을 리턴해주면 된다.

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(d, l, a):
    if l == 2 or a == 3:
        return 0
    if d == n:
        return 1
    if dp[d][l][a] == -1:
        dp[d][l][a] = (dfs(d + 1, l, 0)
                       + dfs(d + 1, l + 1, 0)
                       + dfs(d + 1, l, a + 1))
    return dp[d][l][a]


n = int(input())
dp = [[[-1 for _ in range(3)]for _ in range(2)]for _ in range(n)]

print(dfs(0, 0, 0) % 1000000)

사실 다른 문제 풀다가 못 풀 거 같아서 이 문제로 갈아탄 거다.

아까 풀던 다른 문제보다는 쉬웠다.

골드 4 푸니까 3점 올랐다...

다음부터 골드 3 이상으로 풀어야겠다.