[백준 1446] 지름길 (JAVA)

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

1446번: 지름길

 

1. 지름길 객체를 만들고

1) 시작 위치 오름차순

2) 끝나는 위치 오름차순

3) 거리 오름차순

으로 정렬할 수 있도록 한다.

 

2.ArrayList에 객체를 넣고 정렬 시킨다.

 

3. int배열 dp를 만들고 열의 값으로 초기화한다.

 

4. 지름길 갯수 만큼 포문을 돌려서 dp[시작위치]+거리를 더한 값이 기존의 dp[끝위치]보다 작을 경우,

전체 고속도로의 거리까지 포문을 돌려서 dp값을 재세팅한다.

 

5. 따라서 dp[고속도로거리]가 답이 된다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static class Shortcut implements Comparable<Shortcut>{
		int x,y,dist;
		Dot(int x, int y,int dist){
			this.x=x;
			this.y=y;
			this.dist=dist;
		}
		@Override
		public int compareTo(Shortcut d) {
			if(this.x==d.x) {
				if(this.y==d.y) {
					return this.dist-d.dist;
				}
				return this.y-d.y;
			}
			return this.x-d.x;
		}
	}
	
	static int[] dp=new int[10001];
	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 d=Integer.parseInt(st.nextToken());
		for(int i=0;i<=d;i++) {
			dp[i]=i;
		}
		ArrayList<Shortcut> list = new ArrayList<>();
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			int dist=Integer.parseInt(st.nextToken());
			list.add(new Shortcut(x,y,dist));
		}
		Collections.sort(list);
		int prev=0;
		for(int i=0;i<n;i++) {
			Shortcut dot=list.get(i);
			int x=dot.x;
			int y=dot.y;
			int dist=dot.dist;
			prev=dp[x];
			if(dp[y]>(prev+dist)&&y<=d) {
				dp[y]=prev+dist;
				for(int j=y+1;j<=d;j++) {
					dp[j]=Math.min(dp[j],prev+dist+j-y);
				}
			}
		}
		
		System.out.println(dp[d]);
	}

}