[BOJ] 1563 개근상 (Python3)

문제

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

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

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

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

정답 코드

n = int(input())

answer = 0
dp = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)]

def dfs(day, LCount, ACount):
    if LCount == 2 or ACount == 3:
        return 0
    
    if day == n:
        return 1
    
    if dp[day][LCount][ACount] == -1:
        attend = dfs(day + 1, LCount, 0) + dfs(day + 1, LCount + 1, 0) + dfs(day + 1, LCount, ACount + 1)
        dp[day][LCount][ACount] = attend
        return attend
    else:
        return dp[day][LCount][ACount]
        
        
print(dfs(0, 0, 0)%1000000)

문제 풀이

언뜻 보면 dfs 완전 탐색으로 모든 조합을 구하면 될 것 같은데, N의 조건을 1000보다 작거나 같게 했기 때문에 딱봐도 완전 탐색으로는 시간복잡도를 통과할 수 없다.

그러면 딱봐도 DP로 기록하면서 시간복잡도를 줄여서 풀면 된다.<- 여기 까지는 생각했는데 그래서 어떻게 하는지는 잘 안떠오른다.

생각해보면 문자자체는 이 문제에서 중요하지 않다. LOA와 AOO같은 문자자체를 아예 지우고, 조건에만 집중해보면 지각은 2회 이상하면 안되며 결석은 3번 연속하지만 않으면 개근상을 받을 수 있는 것이다.

따라서 지각수를 LCount, ACount로 정하고 이 숫자가 LCount == 2, ACount가 3이 아닌 경우에만 하루씩 추가해가며 dfs를 다음 단계로 보내 계산하면 된다.

그런데 LOA, OLA, AOL, ALO, OAL, LAO와 같이 결석과 지각수는 똑같은데 순서가 다른경우면 굳이 끝까지 탐색할 필요없이 개근상을 받을 수 있는지 없는지는 이미 계산한 과정이므로, 이미 계산한 LCount와 ACount의 조합이라면 dfs를 보내지말고 dp에 기록된 값을 가져오게 하면 된다. 이렇게 하면 방금 든 예제에서는 6번의 계산을 1번으로 줄일 수 있기 때문에 시간복잡도를 통과할 수 있다.