[BOJ 1029] 그림 교환

문제

---

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

풀이

---

N <= 15이기 때문에 전형적인 비트필드를 이용한 DP이다.

현재 그림의 가격, 그림을 소지했던 사람들의 정보가 정해지면 그 이후는 완전히 독립적인 부분 문제가 된다.

코드

---

import sys

n = int(sys.stdin.readline())
board = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(n)]
dp = [[float('inf')] * n for _ in range(2 ** n)]

res = 1
queue = [(0, 0, 1, 1)]
while queue:
    i, price, mask, num = queue.pop()
    for j in range(n):
        if (not mask & (1 << j)) and (price <= board[i][j]):
            if dp[mask | (1 << j)][j] > board[i][j]:
                dp[mask | (1 << j)][j] = board[i][j]
                res = max(res, num + 1)
                queue.append((j, board[i][j], mask | (1 << j), num + 1))

print(res)

처음에 별생각 없이 메모이제이션도 안 한 채 제출했다가 TLE를 받았다.

브루트포트 방식은 최대 O(N!) : 15! = 1307674368000 (10 ** 13) 경우이므로 당연히 TLE고, 메모이제이션을 하면 최대 O(N * 2 ** N) : 15 * 2 ** 15 = 491520 경우이다.