백준 1311 - 할 일 정하기 1 [Python]

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

1311번: 할 일 정하기 1

DP Using Bitfield

 

dp[n][bit] = (n번째에서 상태가 bit일 때 최소 비용) 이라고 정의하자.

 

dp[n][bit] = min(dp[n][bit], f(n + 1, bit | (1 << i) ) + a[n + 1][bit]) 이 되고, 시간복잡도는 \(O(2^{N}N)\)이 된다.

 

Python3으로는 터진다.

 

템플릿 코드

import sys, math
import heapq
 
from collections import deque
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
#input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
#gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
#prime
def isPrime(x):
    if x<=1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True
 
# Union Find
# p = {i:i for i in range(1, n+1)}
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
def getPow(a, x):
    ret = 1
    while x:
        if x&1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x>>=1
    return ret
 
def getInv(x):
    return getPow(x, MOD-2)

 

INF = 100000000
dp = [[-1 for _ in range(1 << 20)] for _ in range(21)]
def f(x, bit):
    if x == n:
        return 0
    if dp[x][bit] != -1:
        return dp[x][bit]
    dp[x][bit] = INF
    for i in range(n):
        if not bit & (1 << i):
            dp[x][bit] = min(dp[x][bit], f(x + 1, bit | (1 << i)) + a[x][i])
    return dp[x][bit]
 
n = ip()
a = [lmip() for _ in range(n)]
print(f(0, 0))

추가

AC를 받았지만 느리다.

문제의 특징 중 하나는 방문 순서는 상관이 없다는 점이다. 여기서 우리는 dp[n][bit]에서 n을 떼버릴 수 있다.

 

dp[bit] = (상태가 bit일 때 최소 비용) 이라고 정의하면, 공간복잡도를 많이 줄일 수 있다.

 

개선된 코드

INF = 100000000
dp = [-1 for _ in range(1 << 20)]
def f(x, bit):
    if x == n:
        return 0
    if dp[bit] != -1:
        return dp[bit]
    dp[bit] = INF
    for i in range(n):
        if not bit & (1 << i):
            dp[bit] = min(dp[bit], f(x + 1, bit | (1 << i)) + a[x][i])
    return dp[bit]
 
n = ip()
a = [lmip() for _ in range(n)]
print(f(0, 0))