import sys
input = sys.stdin.readline
INF = 10**6
def DFS(bit):
if bin(bit).count("1") >= P:
DP[bit] = 0
return
if DP[bit] != INF:
return
for next in range(N):
if bit&(1<<next):
continue
if DP[bit|(1<<next)]==INF:
DFS(bit|(1<<next))
for now in range(N):
if not bit&(1<<now):
continue
DP[bit] = min(DP[bit],DP[bit|(1<<next)]+graph[now][next])
N = int(input())
graph = []
for i in range(N):
graph.append([*map(int,input().split())])
data = input().strip()
bit = 0
for i in range(N):
if data[i] == "Y":
bit |= 1<<i
P = int(input())
DP = [INF]*(1<<N)
if bit:
DFS(bit)
print(DP[bit])
else:
if P == 0:
print(0)
else:
print(-1)
전형적인 비트마스킹 DP 문제.
발전소가 켜져있는 것과 꺼져있는 것을 비트로 표현하고, DFS+DP로 풀이하면 된다.
알고리즘 자체는 외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 보다 더 쉽다.
DP를 2차원으로 만들어야하는 외판원순회와 다르게 1차원으로도 충분하기 때문
다만 예외처리를 해야하는 부분이 까다로웠는데, 이 문제도 그놈의 0이 문제였다.
맨 처음 시작부터 bit가 0이면 -1을 출력해야하는것과, bit가 0이더라도 P가 0이면 0을 출력해야하는 것, 이 두 가지 때문에 애를 좀 먹었다.
이 점만 주의하면 풀이과정 자체는 어려울게 없다. 왜 이 문제가 플래티넘이고 외판원 순회가 골드인지 이해가 안가는...
오늘의 교훈) 0일때의 예외를 항상 조심, 또 조심