[알고리즘] 백준 13305 주유소 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 실버4
링크 : https://www.acmicpc.net/problem/13305

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 10만 > BufferedReader 사용
O(n) 풀이 > 시간제한 ok
제일 왼쪽 도시 <> 오른쪽 도시 거리 : 10억, 리터당 최대 비용: 10억 > long형 변수 사용 (거리가 10억이고, 리터당 비용이 10억이면 최대 10억^2가 나올 수 있으므로, int로 불가능)

풀이

본인은 그리디 알고리즘에 대해서 실버3정도의 실력을 가져서 그런지, 풀이를 생각하는데 약 5분정도의 시간이 걸렸다. (이정도는 문제를 보자마자 생각해낼 때까지 연습하자)

1. 나중에 들를 도시중에 현재 도시보다 싼 곳을 찾기
1-1. 그런 도시가 있다면, 해당 도시까지 필요한 연료만 구매
1-2. 그런 도시가 없다면, 현재 도시에서 목적지까지 필요한 모든 연료 구매
문제의 사진을 보자. 현재 도시 (제일 왼쪽)의 연료 비용은 5원이다. 이후에 들를 도시중 현재 도시(5원)보다 싼 곳은 바로 다음 도시(2원) 이다. 다음 도시까지 필요한 연료 2리터만 구매하자. (현재 비용: 5x2=10원) 이후, 목적지까지 2원보다 싼 곳은 없으므로, 2원으로 목적지까지 필요한 연료 4리터를 구매하자. (현재 비용 : 10원 + 2x4원 = 18원)

Input Data를 받아준다. stoi메소드는 매번 Integer.ParseInt()를 작성하기 번거로워서 메소드로 만들었다. BufferedReader에 대한 설명은 여기를 참고하자. ans가 long인 이유는, 좌측~우측 최대 거리 10억 * 리터당 최대 비용 10억인 경우 int로 못받기 때문이다.
이후, 목적지 (맨 오른쪽)까지 이동해주면서, 현재 가격보다 저렴한 곳이 있으면 그곳에서 구매하도록 한다.

코드

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long ans = 0;
		
		int n = stoi(br.readLine());
		int[] distArr = new int[n-1];
		int[] priceArr = new int[n];
		
		String[] distStr = br.readLine().split(" ");
		String[] priceStr = br.readLine().split(" ");
		
		for(int i = 0; i < n-1; i++)
			distArr[i] = stoi(distStr[i]);
		for(int i = 0; i < n; i++)
			priceArr[i] = stoi(priceStr[i]);

		int nowIdx = 0;
		while(nowIdx < n) {
			long distSum = 0;
			long nowCost = priceArr[nowIdx];
			for(nowIdx++; nowIdx < n; nowIdx++) {				
				distSum += distArr[nowIdx-1];
				if(priceArr[nowIdx] < nowCost) {
					break;
				}
			}
			ans += (nowCost*distSum);
		}
		System.out.println(ans);
		br.close();
	}
	public static int stoi(String str) {return Integer.parseInt(str);}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.