알고리즘
백트래킹
[1563] 개근상
by Hwang
문제
https://www.acmicpc.net/problem/1563
풀이
모든 경우를 구하려면 매우 많은 시간이 걸립니다. 따라서 이미 구한 조합의 개수를 이용해서 풀이하면 됩니다.
아래 코드의 visited[a_count][l_count][depth] 의 a_count는 연속된 결석(a)의 횟수를 의미하고, l_count는 현재까지의 지각의 횟수를 의미합니다 마지막으로 depth는 현재 날짜를 의미합니다. 예를들어 visited[1][1][9]는 결석이 1번 연속되고 있고, 1개의 지각이 있는 9일차일 때의 개근상을 받을 수 있는 조합의 개수를 의미합니다.
dfs로 탐색을 하며 이미 구한 조합의 개수를 저장해갔고, 이를 이용하여 중복된 탐색을 막아주는 방식으로 풀었습니다.
import sys
sys.setrecursionlimit(10 ** 7)
N = int(sys.stdin.readline())
visited = [[[0] * 1000 for _ in range(2)] for _ in range(3)]
def dfs(depth, l_count, a_count):
if depth == N:
return 1
if visited[a_count][l_count][depth]:
return visited[a_count][l_count][depth]
count = dfs(depth + 1, l_count, 0)
if a_count < 2:
count += dfs(depth + 1, l_count, a_count + 1)
if l_count < 1:
count += dfs(depth + 1, l_count + 1, 0)
visited[a_count][l_count][depth] = count
return count
print(dfs(0, 0, 0) % 1000000)
Comment