[JAVA] BOJ 13305 주유소

출처 : 백준

 

문제가 꽤나 길지만 단순하다. 목적지까지 가기 위해 최소비용으로 기름을 넣는 문제인데, 지금 앞에 있는 주유소가 다음 주유소보다 싸면 더 많이 넣고 더 비싸면 다음 주유소까지 갈 수 있을 정도만 넣고 다음 주유소에서 넣는 것과 같다. 

 

예제 입력 1 예로 들면 기름 리터 당 값이 [5, 2, 4, 1]이고 거리가 [2, 3, 1] 일 때

 

처음엔 무조건 기름을 넣어야 하므로 5를 최솟값으로 저장하고 5의 가격으로 주유한다. 5 * 2 = 10

다음, 최소값인 5와 2를 비교하여 2가 더 작으므로 2를 최솟값으로 저장하고 2의 가격으로 주유한다. 2 * 3 = 6

다음, 최소값인 2와 4를 비교하여 2가 더 작으므로 2를 최솟값으로 저장하고 2의 가격으로 주유한다.  2 * 1 = 2

합은 18이 된다.

 

예제 입력 2는 너무 쉬우므로 다른 예를 살펴보면 기름 리터 당 값이 [1, 2, 3, 4]이고 거리가 [3, 3, 4] 일 때

 

처음엔 무조건 기름을 넣어야 하므로 1을 최솟값으로 저장하고 1의 가격으로 주유한다. 1 * 3 = 3

다음, 최소값인 1과 2를 비교하여 1이 더 작으므로 1을 최솟값으로 저장하고 1의 가격으로 주유한다. 1 * 3 = 3

다음, 최솟값인 1과 3을 비교하여 1이 더 작으므로 1을 최솟값으로 저장하고 1의 가격으로 주유한다. 1 * 4 = 4

합은 10이 된다.

 

이를 코드로 구현하면

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] road = new int[N-1];
		int[] fuel = new int[N];
		for (int i=0;i<N-1;i++) {
			road[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N;i++) {
			fuel[i] = Integer.parseInt(st.nextToken());
		}
		int MIN = Integer.MAX_VALUE;
		long sum=0;
		for(int i=1;i<N;i++) {
			MIN = Math.min(MIN, fuel[i-1]);
			sum += road[i-1]*MIN;
		}
		System.out.println(sum);
	}
}

 

이렇게 제출했더니 58점이 나왔다... 알고 보니 이 문제는 서브 태스크 문제라 일부분이 틀리면 틀렸다가 아니라 부분점수를 준다. 58점이 나왔다는 건 태스크 3번이 틀렸다는 건데 아무런 제약이 없다....?

문제를 다시 들여다보니 주어질 수 있는 숫자가 꽤나 크다. 10억 이하의 자연수이면 이건 int형을 쓰는게 아니라 long 형을 썼어야 한다. 

 

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		long[] road = new long[N-1];
		long[] fuel = new long[N];
		for (int i=0;i<N-1;i++) {
			road[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N;i++) {
			fuel[i] = Integer.parseInt(st.nextToken());
		}
		long MIN = Integer.MAX_VALUE;
		long sum=0;
		for(int i=1;i<N;i++) {
			MIN = Math.min(MIN, fuel[i-1]);
			sum += road[i-1]*MIN;
		}
		System.out.println(sum);
	}
}