[BOJ 20439] 계획왕

문제

---

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

풀이

---

낯익은 바름이가 등장해 친근한 문제였다.

N <= 11이고 K <= 12여서 비트필드에서의 DP인건 알겠는데 파라미터를 뭐로 잡아야 할지 살짝 당황했다.

시간도 1440 크기의 배열로 관리할지, 아니면 (시작 시각, 끝 시각)의 튜플로 관리할지 고민이었다.

현재 시각과 다음날의 일정 사이에 끼워 넣기를 성공한 일의 정보를 담은 비트마스크로 부분 문제가 결정된다.

머릿속으론 잘만 돌아갔는데 구현이 쉽지 않았다.

계속 WA를 받아서 다음날 일정이 없는 구간들을 모아놓은 free 배열을 새로 만들었다.

끼워 넣지 못한 일들 중에 (현재 시각, 현재 시각 + 일을 마치는데 걸리는 시간) 구간이 free 배열의 한 원소에 subset이면 가능하단 식으로 구현했다.

코드

---

import sys

n, k = map(int, sys.stdin.readline().split())

time = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if time and (time[-1][1] == a):
        time.append((time.pop()[0], b))
    else:
        time.append((a, b))

n = len(time)

free = []
if time[0][0] != 0:
    free.append((0, time[0][0]))
for i in range(n - 1):
    free.append((time[i][1], time[i + 1][0]))
if time[-1][1] != 1440:
    free.append((time[-1][1], 1440))

task = list(map(int, sys.stdin.readline().split()))
dp = [[-1] * 1441 for _ in range(2 ** k)]


def f(mask, t):
    if mask == 2 ** k - 1:
        return 1

    for j in range(n):
        a, b = time[j]
        if a <= t < b:
            t = b
        elif t < a:
            break

    if dp[mask][t] != -1:
        return dp[mask][t]

    for i in range(k):
        if not mask & (1 << i):
            t_ = t
            for j in range(len(free)):
                a, b = free[j]
                if (a <= t_) and (t_ + task[i] <= b):
                    if f(mask | (1 << i), t_ + task[i]):
                        dp[mask][t] = 1
                        return 1
                elif t_ <= b:
                    if j + 1 < len(free):
                        t_ = free[j + 1][0]

    dp[mask][t] = 0
    return 0


print(['BAD', 'GOOD'][f(0, 0)])