문제 출저
https://www.acmicpc.net/problem/15748
15748번: Rest Stops
The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st
www.acmicpc.net
문제 풀이
이번 문제는 영어라 구글 번역기와 블로그를 보고 문제를 파악했습니다.
문제에는 농부 존과 그의 친구 개 배시가 길이 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);
}
}
}
문제 출저
https://www.acmicpc.net/problem/15748
15748번: Rest Stops
The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st
www.acmicpc.net
문제 풀이
이번 문제는 영어라 구글 번역기와 블로그를 보고 문제를 파악했습니다.
문제에는 농부 존과 그의 친구 개 배시가 길이 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);
}
}
}
