[JAVA 자바] 13305번 : 주유소

▶ 문제

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

▶ 설명

유가가 작은 도시에서 기름을 많이 저장해서 최소비용으로 목적지에 도착해야하는 문제이다.

 

문제에서 주어진 대로 도시의 유가가 5 2 4 1 인 경우를 볼 때 배열을 만들어서 최소값을 구한 다음에 그 가격으로 남은 거리를 계산하면 되겠거니 쉽게 생각했지만 4 5 2 1 과 같은 경우엔 최소값을 구한 것 만으로 문제가 바로 해결되지 않았다. 

초기에 오는 값을(첫 도시의 원유가) 먼저 어떤 변수에 저장한 다음에 다음 도시를 지나갈 때마다 유가를 비교하여서 작은 가격이 올 때까지 저장해 두었던 유가로 계산하여서 비용을 구하도록 하면 된다.

 

배열 없이도 입력되는 값을 차례로 받을 수 있는 StringTokenizer 의 nextToken() 을 이용하였고, 더이상 입력되는 값이 없을 때까지 반복할 수 있또록 while 문에 hasMoreToken()을 조건으로 걸어 사용하였다.

 

▶ 문제 풀이

🌱 풀이1.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " "); // distance
		StringTokenizer st2 = new StringTokenizer(br.readLine(), " "); // price

		long sp = Long.parseLong(st2.nextToken()); // smallerPrice
		long sum = 0;
		long price, distance;
		while (st.hasMoreTokens()) {
			distance = Long.parseLong(st.nextToken());
			sum += sp * distance;

			price = Long.parseLong(st2.nextToken());
			if (sp > price) {
				sp = price;
			}
		}
		System.out.println(sum);
	}
}

여기서 포인트는 거리와 기름가격 값을 담을 변수를 int 형이 아닌 long 형으로 만들어 주어야 한다는 점이다.

문제에서 제시했듯 리터당 가격과, 도시와의 거리의 범위가 1이상 1,000,000,000으로 지정되어 있다.

 

Integer의 범위는 2,147,483,647까지이므로 제시된 제약범위보다는 작기 때문에 int 형을 사용해도 될 것 같지만, 

int 형끼리 연산을 한 결과 값이 Integer의 최대값을 넘어가게 되면 overflow 가 발생하게 되는데 이 때  제대로 된 값으로 반환하지 않으므로 처음부터 long 형끼리 연산하도록 해야 한다.

이 문제에서, 최대 범위인 10억끼리 연산했을 때 충분히 Integer 범위를 넘기므로 long 형으로 데이터를 저장하도록 한 것이다. 

 

 

 

 

▶ Log

서브태스크가 있는 문제는 처음 풀어보는데 내가 놓칠 수 있는 것을 부분적으로 체크할 수 있어서 좋았다.

처음 제출했을 때 58점을 받았는데 long 형이 아닌 int 형을 썼기 때문이다.

문제를 다시 읽어보니 큰 수의 범위가 지정되어 있어서 이 점을 참고하여 다시 제출을 하니 드디어 통과가 되었다.

문제에서 정해준 범위를 간과하지 않도록 조심해야겠다.