[백준] 15748 Rest Stops - Java

 

 

 

문제 출저

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

15748번: Rest Stops

 

 

 

문제 풀이

이번 문제는 영어라 구글 번역기와 블로그를 보고 문제를 파악했습니다.

문제에는 농부 존과 그의 친구 개 배시가 길이 L의 산을 하이킹 합니다.

n개의 쉬는 지점과 존이 1미터 가는데 걸린 시간, 배시가 1미터 가는데 걸린 시간이 주어집니다.

n개의 쉬는 지점과 쉴 때 얻을 수 있는 풀의 양이 주어집니다.

 

배시는 존 보다 빠르며 존에게 뒤처지면 안됩니다. 

존은 계속해서 하이킹을 하고 배시는 쉬는 지점에서 쉴 수 있습니다. 

이 때, 배시는 쉬면서 풀을 얻을 수 있습니다.

하이킹이 끝났을 때, 배시가 얻을 수 있는 최대 풀의 양을 구해야 합니다. 

 

 

이 문제는 그리디 문제로 가장 많은 풀을 얻을 수 있는 곳을 먼저 가는 곳으로 로직을 구현했습니다.

가장 많은 풀을 얻을 수 있는 곳으로가 풀을 얻고 파머가 오면 다음 장소로 가 풀을 얻습니다. 이 과정을 반복합니다.

 

얻을 수 있는 풀의 양은 (머물 수 있는 시간 * 시간 당 얻을 수 있는 풀의 양) 입니다.

머물 수 있는 시간은 먼저 (풀을 얻을 수 있는 지점 - 현재 지점)을 통해 이동 거리를 구합니다.

그 다음 (이동 거리 * 파머의 1미터 가는데 걸리는 시간) - (이동 거리 * 배스의 1미터 가는데 걸리는 시간) 구하면 머물 수 있는 시간입니다. 

 

쉬는 지점을 풀의 양을 기준으로 내림차순 합니다. 

많이 얻을 수 있는 곳에서부터 얻을 수 있는 풀의 양을 구합니다.

만약 다음 탐색 지점이 현재 탐색 지점 보다 전이면 생략을 합니다. 

 

 

소스 코드

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


/*
Rest Stops
https://www.acmicpc.net/problem/15748

농부 파머와 개 배시가 하이킹을 한다.
배시가 파머보다 빠르고 파머보다 뒤처지면 안된다.
쉬는 장소와 거기서 쉬었을 때 획득할 수 있는 풀의 정보가 주어진다.
즉, 배시는 파머를 기다리면서 풀을 획득할 수가 있다.
하이킹을 완료했을 때 배시가 얻을 수 있는 최대 풀을 구해야 한다.

가장 많이 풀을 얻을 수 있는 곳으로 간다.
파머가 오면 다음 가장 풀을 많이 얻을 수 있는 곳으로 간다.
이 작업을 반복한다.

얻을 수 있는 풀의 양은 (시간 당 얻을 수 있는 풀의 양 * 머물 수 있는 시간) 이다.
머물 수 있는 시간은 먼저 (풀을 얻을 수 있는 지점 - 현재 지점)을 구해 이동 거리를 구한다.
파머의 1미터 가는데 걸린 시간 * 이동 거리 - 배스의 1미터 가는데 걸린 시간 * 이동 거리를 구하면
머물 수 있는 시간을 구할 수 있다.

 */

public class Main {

  static long l, n, f, b;

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    l = Integer.parseInt(st.nextToken());
    n = Integer.parseInt(st.nextToken());
    f = Integer.parseInt(st.nextToken());
    b = Integer.parseInt(st.nextToken());


    List<Stop> stops = new ArrayList<>();

    for(int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      long spot = Long.parseLong(st.nextToken());
      long grass = Long.parseLong(st.nextToken());
      stops.add(new Stop(spot, grass));
    }

    long nowSpot = 0;
    Collections.sort(stops);

    long answer = 0;
    for(Stop stop : stops) {

      if(stop.spot < nowSpot) {
        continue;
      }

      long guri = stop.spot - nowSpot;
      answer += (guri * f - guri * b) * stop.grass;
      nowSpot = stop.spot;
    }

    System.out.println(answer);



  }

  public static class Stop implements Comparable<Stop> {
    long spot;
    long grass;

    Stop(long spot, long grass) {
      this.spot = spot;
      this.grass = grass;
    }

    // 내림차순으로 정렬
    public int compareTo(Stop s) {
      return (int) (s.grass - this.grass);
    }
  }

}