백준 1029 : 그림 교환

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

1029번: 그림 교환

 

사실 이전 포스팅에서 풀었던 외판원 순회 문제 를 찾아 풀어 보며 비트마스크를 이용한 메모제이션을

공부한 것이 본 문제에서 막혔기 때문이다!

 

해결 방법 : DP 메모제이션

• 메모제이션을 적용하기 위해 외판원 순회 문제에서 사용한 비트마스크에 하나의 차원을 추가해 주어야한다.
  • 같은 node 시점에서 같은 path로 구성되어 있다고 해도, 현재 그림의 가격에 따라 다음으로 그림을 구매할 artist가 바뀌기 때문이다.
  • 따라서 메모제이션은 [현재 artist][현재까지 구입한 artist path][현재 그림 price]의 3차원 배열에 적용된다. 

본 문제는 완전 탐색으로는 시간 초과가 발생하여, 메모제이션을 적용해야만 한다.

하지만, 메모제이션으로 시간 단축이 가능한 이유는 그림 가격이 0~9로 좁은 범위를 가지기 때문이다.

솔직히 더 많은 알고리즘 기법을 억지로 적용하게 만든 느낌이다.

(기본 외판원 순회 문제의 경우, 메모제이션 적용으로 인한 탐색 횟수 감소가 확연하다.)

 

import sys
input = sys.stdin.readline

def solution(n, arr):
    M = [[[0] * 10 for j in range(1 << n)] for i in range(n)] # M[artist][path(bin)][price]

    def dfs(artist, path, price):
        if M[artist][path][price] != 0: # 메모제이션 적용
            return M[artist][path][price]

        count = 0 # 현재 artist 부터의 최대 거래 횟수
        for nextA in range(1, n):
            if arr[artist][nextA] < price or path & (1 << nextA) > 0: 
                continue
            count = max(count, 1 + dfs(nextA, path | (1 << nextA), arr[artist][nextA]))
        M[artist][path][price] = count # 메모!

        return count

    return 1 + dfs(0, 1, 0) 

if __name__ == '__main__':
    n = int(input())
    arr = []
    for i in range(n):
        arr.append([int(j) for j in input().strip()])
    result = solution(n, arr)
    print(result)