[DP]여행(백준 2157번), 자바(ㅁㅁㅁ)

2157번: 여행 (acmicpc.net)

2157번: 여행

 

간단한거였는데, 오래걸렸다.

import java.util.*;

public class Main{

	
	
	public static void main(String[] args) {
		int N,M,K;
		int[][] dp;
		int answer=0;
		PriorityQueue<Point> q=new PriorityQueue<>(new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				// TODO Auto-generated method stub
				return o1.x-o2.x;
			}
			
		});
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		K=sc.nextInt();
		
		dp=new int[N+1][M+1];
		
		for(int i=1;i<=K;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			int point=sc.nextInt();
			if(x==1) dp[y][1]=Math.max(dp[y][1],point); //1에서 출발하는 경우 
			else q.add(new Point(x,y,point));
		}
		
		
		while(!q.isEmpty()) {
			Point p=q.poll();
			for(int i=1;i<M-1;i++) {
				if(dp[p.x][i]!=0) dp[p.y][i+1]=Math.max(dp[p.y][i+1],dp[p.x][i]+p.point);
				else continue;
			}
		}
	
		
		for(int i=1;i<M;i++) {
			answer=Math.max(answer, dp[N][i]);
		}
		System.out.println(answer);

	}
	
	static class Point{
		int x;
		int y;
		int point;
		
		public Point(int x, int y, int point) {
			this.x=x;
			this.y=y;
			this.point=point;
		}
	}
	
	
}