백준 스키장(22358)

스키장

1. 힌트

1) 주어진 그래프는 DAG입니다. DP를 적용할 수 있습니다.

2) 역방향 간선을 따로 저장하면 쉽게 구현할 수 있습니다.

2. 접근

1) DAG

간선은 $a_i < b_i$인 $(a_i, b_i)$를 잇기 때문에, 그래프로 생각한다면 사이클이 존재할 수 없습니다.
하지만 리프트는 $b_i < a_i$인 $(b_i, a_i)$를 잇긴 하지만, 리프트는 최대 $0 \le K \le 10$번 탈 수 있으므로 정점을 (번호, 리프트를 탈 수 있는 남은 횟수)로 정의하면 같은 정점으로 다시는 돌아올 수 없습니다. 여기까지 확인했으면 나머지는 메모이제이션을 적용해 DP로 구현하는 것입니다.

3. 구현

dp함수에서 max는 충분히 작은 값으로 초기화해서 $T$에 도달할 수 없는 경우를 제외해줘야 합니다. 또한 $T$번 정점에 도달했더라도 $k =0$이 아니라면 도달한 정점을 그대로 돌아가면되므로 base case는 $i = T,k = 0$일때로 정의합니다

이 문제는 자바 추가시간이 없기 때문에 자바로 풀 수 없습니다! 대회에서는 이 코드를 c++로 번역해서 제출했습니다.

public class Main {
	static int T;
	static long[][] cache;
	static ArrayList<ArrayList<Pair>> adj;
	static ArrayList<ArrayList<Pair>> adj2; // 역방향 간선
	
	// i번째 지점에서 k번 리프트를 탈 수 있을 때 T까지 가는 최장경로
	static long dp(int i, int k) {
		if (i == T && k == 0) return 0;
		if (cache[i][k] != -1) return cache[i][k];
		long max = Long.MIN_VALUE;
		if (k > 0)
			for (Pair edge : adj2.get(i)) 
				max = Math.max(max, dp(edge.num, k - 1));
		for (Pair edge : adj.get(i)) {
			int there = edge.num; int cost = edge.cost;
			max = Math.max(max, cost + dp(there, k));
		}
		return cache[i][k] = max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		adj = new ArrayList<>(N + 1); adj2 = new ArrayList<>(N + 1);
		for (int i = 0; i <= N; i++) {
			adj.add(new ArrayList<>());
			adj2.add(new ArrayList<>());
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			adj.get(a).add(new Pair(b, t));
			adj2.get(b).add(new Pair(a, 0));
		}
		cache = new long[N + 1][K + 1];
		for (int i = 0; i < N + 1; i++) Arrays.fill(cache[i], -1);
		long ret = dp(S, K);
		if (ret < 0) ret = -1;
		System.out.println(ret);
	}

}
class Pair {
	int num, cost;
	Pair (int n, int c) { num = n; cost = c; }
}