[BOJ] 13305 주유소

13305번: 주유소 (acmicpc.net)

40줄 안되는 코드로 풀 수있었다.
문제를 처음 봤을때는 정렬을 이용해서 풀려고 했다.
가장 가격이 싼 지점에서 끝까지 한번에 방문한 값과, 그 지점 이전까지의 합을 더해서 계산하려고했다.
그러다가 이전 비용들을 계산하는 과정에서 굳이 지점을 나눌필요가 없다는 생각이 들었다.

  1. 이전보다 다음 주유소 가격이 싼 경우
    (최소 가격 * 다음 주유소까지 거리) 를 비용에 누적시키고, 최소 가격을 다음 주유소의 가격으로 업데이트 시킨다.
  2. 다음 주유소 가격이 비싼 경우
    (최소 가격 * 다음 주유소까지 거리) 를 비용에 누적시킨다.

이 작업을 처음부터 끝까지 반복해주면 된다.
처음에는 이걸 구현하기 위해 스택이 필요한줄 알았지만, 스택을 이용해서 구현하고 보니 아니었다.
단순히 최저 가격을 저장하고 있을 변수만 선언해주고, 이를 업데이트 해주거나 그대로 유지시키면서 비용을 계산하고 누적하면 되었다.

가장 큰 함정은 자료형이었다.

입력의 범위가 심상치 않다.
곱 연산이 있기 때문에 충분히 int 의 범위를 벗어나 오버플로우가 발생할 수 있다.
그렇기 때문에 long 자료형으로 누적시키는 값을 선언해주었다.

스택을 이용한 풀이

package com.algo.boj;

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

public class BOJ13305FuelStation {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] distance = new int[N-1];
		for (int i = 0; i < distance.length; i++) {
			distance[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		Stack<Long> stack = new Stack<>();
		stack.push(Long.parseLong(st.nextToken()));
		long sum = 0;
		for (int i = 1; i < N; i++) {
			long tempcost = Long.parseLong(st.nextToken()); //코스트
			if(stack.peek()>= tempcost) { //입력이 기존보다작은 경우
				sum += stack.pop()*distance[i-1];
				stack.push(tempcost);
			}else { 					//입력이 기존보다 큰 경우
				sum += stack.peek()*distance[i-1];
			}
		}
		System.out.print(sum);
	}

}

스택없이 풀이

package com.algo.boj;

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

public class BOJ13305FuelStation2 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] distance = new int[N-1];
		for (int i = 0; i < distance.length; i++) {
			distance[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		long top =Long.parseLong(st.nextToken());
		long sum = 0;
		for (int i = 1; i < N; i++) {
			long tempcost = Long.parseLong(st.nextToken()); //코스트
			if(top>= tempcost) { //입력이 기존보다작은 경우
				sum += top*distance[i-1];
				top = tempcost;
			}else { 					//입력이 기존보다 큰 경우
				sum += top*distance[i-1];
			}
		}
		System.out.print(sum);
	}

}