[백준] 1029 그림 교환

문제 링크

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

사용 알고리즘

• DP
• 비트필드를 이용한 다이나믹 프로그래밍
• 그래프 이론

풀이

이 문제를 해결하기 위해 DP 배열에 저장해야 할 정보는 3가지이다.

• 현재 그림을 가지고 있는 사람: 다음 거래의 가격을 결정하기 위해 필요하다.
• 직전에 거래된 가격: 다음 거래의 가격이 직전 거래의 가격보다 크거나 같은지 확인하기 위해 필요하다.
• 지금까지 지나온 사람들: 이미 거래한 사람들에게 다시 거래하지 않기 위해 필요하다.

이 3가지 조건에 따라 그림을 가지고 있던 사람의 최대값이 달라지게 된다.

 

DP 배열 내의 각 정보들의 크기는 아래와 같이 잡는다.

• 현재 그림을 가지고 있는 사람: n명
• 직전에 거래된 가격: 10 (최대 가격이 10이기 때문에)
• 지금까지 지나온 사람들: 1 << n (비트필드를 이용해서 지금까지 지나온 사람들을 기록 / 사람 수가 n명이기 때문에 1 << n 사이즈의 비트필드 생성)

 

따라서, `dp[now][price][log] = 현재까지 그림을 가지고 있던 사람 수`로 두고 그래프를 탐색해서 조건에 맞는 경우 dp 배열과 정답을 갱신한다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n = int(input())
arr = [[*map(int, input())] for _ in range(n)]

dp = [[[0] * (1 << n) for _ in range(10)] for _ in range(n)]
dp[0][0][0] = 1
s, res = [(0, 0, 0)], 0
while s:
    now, price, log = s.pop()
    
    for nxt in range(n):
        n_price, n_log = arr[now][nxt], (log | (1 << now))

        if (
            now == nxt or
            price > n_price or
            (log & (1 << nxt)) or
            dp[nxt][n_price][n_log]
        ): continue

        dp[nxt][n_price][n_log] = dp[now][price][log] + 1
        res = max(res, dp[nxt][n_price][n_log])
        s.append((nxt, n_price, n_log))

print(res)