백준 13305 - 주유소 JAVA

문제, 입출력

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_13305 {
	public static void main(String[] args) throws NumberFormatException, IOException {
//		2<= 도시의 개수(N) <= 100,000, 1 <= 도시의 거리 <= 1,000,000,000, 1 <= 리터당 가격 <= 1,000,000,000 
//		-> 최대 1,000,000,000,000,000,000 => long 선업 
//		일단 맨 처음 도시에서는 무조건 기름을 넣어야함 -> 얼만큼? -> 최소값을 지닌 도시까지의 거리 만큼
//		맨 처음의 도시가 가장 쌀 경우에는 그냥 거리 x 첫번째 도시 가격만큼 
//		아닐 경우 그 다음 싼 도시까지의 거리 x 첫번째도시 가격 + 마지막 도시의 거리까지 * 그다음 싼도시의 가격
// 		이번 보다 더 싼 값으로 팔면 그때그때 넣기!

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		int N = Integer.parseInt(br.readLine());
		long answerCost = 0L;
		long distance[] = new long[N - 1];
		long fuelPrice[] = new long[N-1];

		stz = new StringTokenizer(br.readLine());
		for (int i = 0; i < distance.length; i++) {
			distance[i] = Long.parseLong(stz.nextToken());
		}
		
		stz = new StringTokenizer(br.readLine());
		for (int i = 0; i < fuelPrice.length; i++) {
			if (i == 0) {
				fuelPrice[i] = Long.parseLong(stz.nextToken());
			} else {
				fuelPrice[i] = Long.parseLong(stz.nextToken());
				if (fuelPrice[i - 1] <= fuelPrice[i]) { // 더 싸거나 같다
					fuelPrice[i] = fuelPrice[i - 1];
				}
			}
			
			answerCost += fuelPrice[i] * distance[i];
		}
		System.out.println(answerCost);

	}
}

테스트케이스

해당 문제는 무척 쉬웠다. 처음에는 PriorityQueue까지 구현해서 풀까도 했지만 그냥 아이디어가 바로 떠올라버려서 풀어제꼈다.

바로 본론으로 들어간다!

 

<문제 접근/풀이 과정>
1. 2<= 도시의 개수(N) <= 100,000, 1 <= 도시의 거리 <= 1,000,000,000, 1 <= 리터당 가격 <= 1,000,000,000 
2. -> 최대 1,000,000,000,000,000,000 => long 선언
3. 일단 맨 처음 도시에서는 무조건 기름을 넣어야함 -> 얼만큼? -> 최소값을 지닌 도시까지의 거리 만큼? / 그 다음으로 기름값이 싼 도시까지의 거리만큼?
4. 맨 처음의 도시가 가장 쌀 경우에는 그냥 거리 * 첫번째 도시 가격만큼 
5. 아닐 경우 그 다음 싼 도시까지의 거리 * 첫번째도시 가격 + 그 다음 거리* 그다음 싼도시의 가격
6. 아니다! 결국 이번 보다 더 싼 값으로 팔면 그때그때 넣는 것이 제일 좋겠다.
ex) 5 4 3 2 1 2 4 5가 기름값이면 -> 5 4 3 2 1 1 1 1 이런식으로 이전 도시보다 기름값이 싼 경우에만 해당 도시의 기름 값을 할당해 버리면 된다.

그리디 알고리즘 까지 완~료

 

단계별로 풀어보기의 그리디 알고리즘은 다 풀어제꼈으나, 그리디는 그냥 틈만 나면 나오는 것이기 때문에 결국 아이디어 문제라고 생각한다. 경계를 늦추어선 안된다..!

내일부터는 무시무시한 정수론 및 조합론이다 ㅜㅜ 이론을 모르면 못 푸는 마의 영역 

화이팅!