[BOJ 9520] NP-hard

문제

---

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

풀이

---

비트마스킹 + DP로 푸는 기존의 외판원 순회 문제 외판원 순회와는 다르게 N의 제한이 1500까지 늘어났다.

대신 이런 조건이 붙었다.

‘번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다. 즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안 된다.’

조금 생각해 보면 방문한 도시 번호의 수열은 monotonically decrease하다 monotonically increase하는 형태로 나타남을 알 수 있다.

지금 생각해 보면 말도 안 되지만 처음엔 1차원 DP로 풀려고 했다.

f(i) : i번 도시에서 시작해 1 ~ i번 도시를 모두 방문할 때의 최소 비용

금방 불가능하다는 것을 깨닫고 변수를 하나 더 추가해봤으나 점화식이 너무 더럽게 나왔다.

f(i, j) : i번 도시에서 시작해 1 ~ i번 도시를 모두 방문하고 j번 도시에 도착할 때의 최소 비용

머리를 비우고 처음부터 다시 시작했다.

위에서 언급했던 V자 모양의 방문 도시 수열과 연관 지어 생각해 보니, 가운데 1에서 시작해서 2, 3, 4…를 차례로 왼쪽 혹은 오른쪽에 이어붙여만든 수열과 일대일대응 됨을 알 수 있었다.

생각의 전환이 이뤄지니 문제가 엄청나게 간결해졌다.

코드

---

import sys

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]


def tsp(left, right):
    num = max(left, right) + 1
    
    if num == n:
        return 0
    
    if dp[left][right]:
        return dp[left][right]

    res = min(graph[num][left] + tsp(num, right), graph[right][num] + tsp(left, num))

    dp[left][right] = res
    return res


print(tsp(0, 0))

Recursion Limit

---

pypy3을 사용하는 입장에서, 특히 DP문제를 풀 때 RecursionError가 안 나게 하면서도 메모리가 터지지 않게 recursion limit을 조절해 줘야 한다.

문제의 메모리 제한마다 다르겠지만, 경험상 10 ** 5까진 괜찮았던 것 같다.

이 문제의 경우엔 maximum recursion depth = 1500이다.

sys.getrecursionlimit()

# Out : 1000

python3은 default recursion limit이 1000이다.

그래서 recursion limit을 따로 설정하지 않고 제출하면 RecursionError가 뜬다.

하지만 pypy3은 recursion limit 설정 없이 제출해도 통과가 된다.

pypy3은 sys.setrecursionlimit()이 안 먹힌다는 얘기도 많은데, 이 코드의 유무가 AC/WA를 가렸던 경험도 있던 것 같다.

나중에 한 번 각 잡고 알아봐야겠다.