Life Engineering
[BOJ 13305] 주유소 (Java) 본문
https://www.acmicpc.net/problem/13305
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_BOJ_13305 {
static int N;
static long[] dist;
static long[] prices;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
N=Integer.parseInt(br.readLine());
prices=new long[N];
dist=new long[N-1];
st=new StringTokenizer(br.readLine());
for (int i=0; i<N-1; i++) {
dist[i]=Long.parseLong(st.nextToken());
}
st=new StringTokenizer(br.readLine());
for (int i=0; i<N; i++) {
prices[i]=Long.parseLong(st.nextToken());
}
long min=Long.MAX_VALUE;
long sum=0;
for (int i=0; i<N-1; i++) {
if (prices[i]<min) { //최소값 발견 시 그걸로 사기
min=prices[i];
}
sum+=(min*dist[i]);
}
System.out.println(sum);
}
}
그리디 알고리즘.
최소값 발견 시 그걸로 갱신하고, 그것보다 작은 값을 발견할때까지 쭉 그걸로 구매하는 방식이다.
범위 설정에 유의하자.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 후보키 (Java) (0) | 2022.03.01 |
---|---|
[프로그래머스] 삼각 달팽이 (Java) (0) | 2022.03.01 |
[BOJ 17822] 원판 돌리기 (Java) (0) | 2022.02.25 |
[BOJ 17143] 낚시왕 (Java) (0) | 2022.02.24 |
[BOJ 16236] 아기 상어 (Java) (0) | 2022.02.23 |