99클럽 코테 스터디 27일차 TIL (챌린저): [백준][Java] 1446 지름길 - 실버1

 

문제 보기

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

 

 

풀이

DP를 사용해 문제를 풀었다.

지름길과, 이전 칸에서 +1을 하는 것 중 무엇이 빠른지를 계속 비교하였다.

    for(int i = 1; i <= D; ++i) {
      dp[i] = dp[i - 1] + 1;
      for(int j = 0; j < list[i].size(); ++j) {
        dp[i] = Math.min(dp[i], dp[list[i].get(j)[0]] + list[i].get(j)[1]);
      }
    }

핵심 코드는 위와 같다.

list[]은 i까지 도착하기 위한 출발 지점, 걸리는 시간을 담고 있다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int D = Integer.parseInt(st.nextToken());

    int[] dp = new int[D + 1];
    dp[0] = 0;
    List<int[]>[] list = new ArrayList[D + 1];
    for(int i = 1; i <= D; ++i) {
      list[i] = new ArrayList<>();
    }

    for (int i = 0; i < N; i++) {
      String[] line = br.readLine().split(" ");
      if(Integer.parseInt(line[1]) > D) continue;
      list[Integer.parseInt(line[1])].add(new int[]{Integer.parseInt(line[0]), Integer.parseInt(line[2])});
    }

    for(int i = 1; i <= D; ++i) {
      dp[i] = dp[i - 1] + 1;
      for(int j = 0; j < list[i].size(); ++j) {
        dp[i] = Math.min(dp[i], dp[list[i].get(j)[0]] + list[i].get(j)[1]);
      }
    }

    bw.write(dp[D] +"");

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/1446.%E2%80%85%EC%A7%80%EB%A6%84%EA%B8%B8

CodingTest_AutoSave/백준/Silver/1446. 지름길 at main · MetroDefro/CodingTest_AutoSave