[백준] 1446 지름길

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

1446번: 지름길

1. 유형

완전탐색, 다익스트라

 

2. 풀이

첫번째 풀이, 완전탐색

총 12개의 값만 주어지기 때문에 완전탐색으로 충분히 구할 수 있다.

1. 시작, 도착지 기준으로 정렬

2. 선택을 하는 경우, 안 하는 경우로 나누어 모든 경우 탐색

import java.io.*;
import java.util.*;

public class Main {
	static List<int[]> list;
	static int N, D, res;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		list = new ArrayList<>();
		N=stoi(st.nextToken());
		D=stoi(st.nextToken());
		res = Integer.MAX_VALUE;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = stoi(st.nextToken());
			int b = stoi(st.nextToken());
			int c = stoi(st.nextToken());
			list.add(new int[] {a, b, c});
		}
		Collections.sort(list, (o1, o2)->{
			return o1[0]-o2[0];
		});
		recur(0, 0, 0);
		System.out.println(res);
	}
	static void recur(int h, int end, int sum) {
		if(h == N) {
			if(end > D) {
				return;
			}else if(end==D){
				res = Math.min(res, sum);
			}else {
				res = Math.min(res, sum+D-end);
			}
			return;
		}
		int arr[] = list.get(h);
		if(arr[0] >= end) {
			recur(h+1, arr[1], sum+arr[2]+arr[0]-end);
		}
		recur(h+1, end, sum);
	}
	
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

 

두번쨰 풀이, 다익스트라

1씩 증가하면서 지름길이면 다익스트라 적용

1. 현재값 갱신

2. 지름길이 더 작으면 갱신

import java.io.*;
import java.util.*;

public class Main {
	static List<int[]> list[];
	static int N, D, res;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N=stoi(st.nextToken());
		D=stoi(st.nextToken());
		list = new ArrayList[10001];
		for(int i=0; i<list.length; i++) {
			list[i]=new ArrayList<>();
		}
		res = Integer.MAX_VALUE;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = stoi(st.nextToken());
			int b = stoi(st.nextToken());
			int c = stoi(st.nextToken());
			list[a].add(new int[] {b,c});
		}
		int dp[] = new int[10001];
		init(dp);
		for(int i=0; i<=D; i++) {
			if(i!=0)
				dp[i]=Math.min(dp[i-1]+1, dp[i]) ;
			if(list[i].size()>0) {
				for(int tmp[]: list[i]) {
					int val = tmp[1];
					int end = tmp[0];
					if(dp[end] > dp[i]+val) {
						dp[end] = dp[i]+val;
					}
				}
			}
			
		}
		System.out.println(dp[D]);
	}
	static void init(int arr[]) {
		for(int i=0; i<arr.length; i++) {
			arr[i]=i;
		}
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}