BOJ#9520 NP-Hard

BOJ#9520 NP-Hard

* 문제

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

* 풀이

- 규칙 : 번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다.

즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안된다.

위 규칙을 만족하는 방문 수열은 아래와 같이 만들 수 있습니다.

맨 처음 1번 도시를 방문 : {1}

그 다음 2번 도시는 수열의 왼쪽 또는 오른쪽에 들어갈 수 있습니다 : {2, 1}, {1, 2}

그 다음 3번 도시는 수열의 왼쪽 또는 오른쪽에 들어갈 수 있습니다 : {3, 2, 1}, {2, 1, 3}, {3, 1, 2}, {1, 2, 3}

그 다음 4번 도시는 ...

즉, 각각의 도시는 왼쪽에 붙을지, 오른쪽에 붙을지 선택하면 됩니다. 그리고 선택의 기준은 N번 도시를 방문할 때까지의 cost가 작은 쪽으로 선택하면 됩니다.

그리고 각 도시를 수열에 붙이기 위해서는 수열의 왼쪽, 오른쪽 도시가 무엇인지 알고 있을 필요가 있습니다.

dp[left][right] : 양 끝이 left, right인 방문 수열에서 N번째 도시까지 방문했을 때, 최소 비용

solve(left, right) : dp[left][right]를 리턴하는 재귀 함수

int next = max(left, right) + 1;

dp[left][right] = min(next를 왼쪽에 붙이는 경우, next를 오른쪽에 붙이는 경우) = min(weight[next][left] + solve(next, right), weight[right][next] + solve(left, next)

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%239520_NP-Hard/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ#9520 NP-Hard
 * https://www.acmicpc.net/problem/9520
 */

public class Main {

    static final int FRONT = 0;
    static final int BACK = 1;
    static final int MIN = 2;

    static int N;
    static int[][] weight = new int[1501][1501];
    static int[][] dp = new int[1501][1501];

    static {

        for (int i = 0; i < 1501; i++) {

            Arrays.fill(dp[i], -1);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for (int i = 1; i < N + 1; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j < N + 1; j++) {

                weight[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(solve(1, 1));

    } // main

    static int solve(int left, int right) {

        if (dp[left][right] >= 0) return dp[left][right];

        int next = Math.max(left, right) + 1;

        if (next > N) return 0;

        return dp[left][right] = Math.min((weight[next][left] + solve(next, right)), (weight[right][next] + solve(left, next)));
    }
}