Python으로 푸는 백준 1563. 개근상

백준 1563. 개근상

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

백준에서 푼 문제 리스트

백준에서 문제 보기

Github에서 코드

문제 조건

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

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

문제 풀이

문제의 조건을 이해해 보자. 지각 횟수는 누적되고, 결석은 연속되지 않으면 초기화된다. 주어진 한 학기 출결 일 수 N일까지, 1일부터 차근차근 경우의 수를 살펴나갈 것이다. 매일 현재의 지각 횟수, 연속 결석 수를 확인하여, 문제 조건에 제시된 '개근상을 받을 수 없는 조건'에 해당되지는 여부를 확인한다. 이처럼 N일까지 매일 조건을 체크하면서 개근상을 받는 것이 가능한 경우의 수를 찾아 늘려가기 위하여 DP(큰 문제를 작은 문제로 쪼개 작은 문제부터 해결해 나가는 방법)를 적용해 문제를 풀어나간다.

 매일 학생이 할 수 있는 출결 사항은 (1) 출석 (2) 지각 (3) 결석 3가지 경우의 수가 있다. N일까지 학생이 만들어 낼 수 있는 출결 기록의 경우의 수는 대층 생각했을 때 3^n 만큼이며 모든 경우의 수를 다 탐색한다고 한다면 그만큼의 재귀가 일어나야 한다(재귀 한도 초과가 예상). 이 문제에서는 최대한 재귀하는 수를 줄이기 위해선 여러가지 가지 치기가 필요하다. 다시 사용하는 값은 memoization 해주어야 하고(가지치기1), 지각을 두번 이상하였거나 결석을 3번 연속으로 한 경우에는 개근상을 받지 못하므로 0을 반환해주어서 불필요한 값을 더 이상 구하지 않도록 해줘야 한다(가지 치기2).

그렇다면 어떠한 값을 다시 사용하게 될거라 생각해 Memoization은 뭘 기록해주어야 하나. Memoization에는 K일째 되는날, 지각과 연속된 결석의 수를 고려하였을 때 N일까지 도달했을 때 개근상을 받을 수 있는 경우의 수를 기록할 것이다.  

Key : Value (K일, 지각한 횟수, 연속된 결석 수) : N일이 되었을 때, 개근상을 받을 수 있는 경우의 수

 

메모이제이션은 한번 계산 해둔 값을 재사용하기 위함이라고 이미 말한 적이 있다. 백준에 나와있는 4일을 예를 들어서 Memoization에 어떤 값을 저장하는지 보면 다음과 같다. 

Memoization한 Memo의 원소들 {(3, 0, 0): 3, (3, 1, 0): 2, (3, 0, 1): 3, (2, 0, 0): 8, (3, 1, 1): 2,  (2, 1, 0): 4, (3, 0, 2): 2, (2, 0, 1): 7, (1, 0, 0): 19, (3, 1, 2): 1,  (2, 1, 1): 3, (1, 1, 0): 7, (2, 0, 2): 5, (1, 0, 1): 17, (0, 0, 0): 43}

Memoization에서 (0, 0, 0): 43의 의미는 0일 째에 지각도 없고, 연속된 결석도 없는 상태에서 N인 4일 째까지 개근상을 탈 수 있는 경우의 수를 모두 구한 값이다. (0, 0, 0)일때의 결과 값을 구하기 위해서는 1일 차에 출석(1, 0, 0), 지각(1, 1, 0), 결석(1, 0, 1)일 경우에 대한 모든 경우의 수를 구해야 하고,  출석(1, 0, 0)에 대한 경우의 수를 구하기 위해선 2일 차에 출석(2, 0, 0), 지각(2, 1, 0),  결석 (2,0,1)의 경우의 수를 합치면 된다. 결국 1일째부터의 모든 경우의 수를 구하는 문제를 2일째, 3일째, 4일째의 경우의 수를 각각 구하는 작은 문제로  나눠서 문제를 해결하며, 이러한 과정에서 중복되는 Key 값에 대해선 이미 계산한 값을 가져다가 쓰는 것이다. 이에 대해 실제로 모든 경우의 수를 그려서 구해보면 다음과 같다.

그림을 이해하기 위해서 하는 설명

형광펜으로 색칠한 Key 값들은 중복되기 때문에 Memoization에서 값을 기록하여 나중에는 재연산 없이 값을 가져다가 쓸 것이다. 잘 보면 1일차에 출석하였을 때 구해진 값들은, 1일차에 결석을 했을 때의 값을 구할 때 대부분 다시 구해야 하기 때문에 Memoization을 활용할 경우 연산의 양을 확실히 줄일 수 있음을 알 수 있다.

파란색으로 동그라미 친 경우는 해당 조건으로 N일까지 출결하여 개근상을 받을 수 있는 경우의 수이다. 1일차 출석(19) = 2일차 출석(8) + 2일차 지각(4) + 2일차 결석(7)이라는 사실을 보고 나면 DP를 이해가기가 더 쉽다.

빨간 줄이 그어진 경우는, 개근상을 받을 수 있는 조건에 위배된 케이스이다. 

ㄴ 1일 차에 출석 했을 때의 모든 경우의 수 (19가지)

ㄴ 1일 차에 지각 했을 때의 모든 경우의 수 (7가지)

ㄴ 1일 차에 결석 했을 때의 모든 경우의 수 (17가지)

이 문제는 DP에 대한 감을 잡기 위하여 모든 경우의 수를 직접 그려서 확인해보았고 결과적으로 매우 도움이 되었다. DP 문제가 이해가 되지 않아서 이 포스팅을 찾으신 분들이라면 쉬운 DP 문제를 찾아서 작은 케이스의 모든 경우의 수를 직접 구해보면 DP의 단짝인 Memoization을 어떤 값을 저장해놔야 할지에 대해서도 감이 잡힐 거라고 생각한다. 

그럼에도 불구하고 런타임 에러가 날 경우

주어진 N이 1,000일 경우에는 파이썬에서 정해놓은 재귀호출 수보다 많은 호출이 일어나면서 RecursionError가 나게 되어 런타임 에러가 날 수도 있다. 의도적으로 파이썬의 재귀호출 수를 증가시키자. 사실 백준의 대다수 문제들이 다른 언어와 같은 알고리즘으로 풀더라도 재귀호출 에러가 나는 경우가 많은 것 같다. 내 알고리즘에 확신이 있을 경우에는나는 재귀 호출 수를 늘려본다. 그럼 대부분 맞다.

sys.setrecursionlimit(1000000000)

파이썬 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)
memo = {} # memoization
 
def dp(total, day, late, abs):
 
    # 지각이 2번 이상이면 fail
    if 2 <= late:
        return 0
 
    # 결석 3연속이면 fail
    if 3 <= abs:
        return 0
 
    # 개근상 조건 충족
    if day == total:
        return 1
 
    # memoization 기록 가져오기
    # day, late, abs가 다음과 같은 값일 경우 개근상을 받을 수 있는 경우의 수
    if (day, late, abs) in memo:
        return memo[(day, late, abs)]
 
    # day째 되는 날에, 그 이후 날들에 출석하거나 지각하거나,결석하였을 때 개근상을 받을 수 있는 경우의 수에 대한 기록
    memo[(day, late, abs)] = dp(total, day + 1, late, 0) + dp(total, day +1, late +1, 0) + dp(total, day +1, late, abs + 1)
    return memo[(day, late, abs)]
 
 
if __name__ == "__main__":
    total = int(input().strip())
    # 출석 일 수, 지각수, 연속 결석 수
    print(dp(total, 0, 0, 0) % 1000000)