[백준알고리즘-JAVA]13305번 풀이(주유소) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 13305번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 13305 (주유소)

 

 주유소 알고리즘은 그리디 알고리즘의 일부로 서브 테스트가 존재하는 새로운 유형의 문제였다. 성공률을 보면 그리 낮은 문제가 아님으로 잘 고심한다면 쉽게 풀이할 수 있는 문제이다. 물론 이런 문제가 어렵다면, 더 많은 알고리즘을 풀면 그만이다!! 알고리즘을 보고 고심하고 풀어보고 하다 보면, 어느샌가 익숙해져 있는 자신을 보게 될 것이다.

 

 주유소 알고리즘에서 중요한 점은 문제 그대로를 정확히 인식하고 차례대로 따라가면 된다. 여기서 주의할 점은 서브 테스트이다. 문제를 다시 한번 되새기고 아래 STEP부분을 따라가 보며 이해해보자

 

딴말은 그만하고 바로 본론으로 들어가 보자

---

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

 

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

 

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총비용은 30원이다.30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2 × 5 = 10원) 다음번 도시까지 이동한 후 3리터의 기름을 넣고(3 × 2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1 ×4 = 4원) 제일 오른쪽 도시로 이동하면, 총비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2 × 5 = 10원) 다음번 도시까지 이동한 후 4리터의 기름을 넣고(4 × 2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

 

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

서브 태스크

번호	배점	제한
1	17	모든 주유소의 리터당 가격은 1원이다.
2	47	2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.
3	42	원래의 제약조건 이외에 아무 제약조건이 없다.

입력 예제

4
2 3 1
5 2 4 1

출력 예제

18

입력 예제

4
3 3 4
1 1 1 1

출력 예제

10

성공 코드

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

public class Main {

	static int N;
	static long[] street;
	static long[] country;
	static long ans;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		street = new long[N-1];
		country = new long[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringTokenizer str = new StringTokenizer(br.readLine());
		
		for(int i = 0 ; i < N-1 ; i++) {
			street[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 0 ; i < N ; i++) {
			country[i] = Integer.parseInt(str.nextToken());
		}
		
		long gas = country[0];
		ans = country[0]*street[0];
		
		for(int i = 1 ; i < country.length-1 ; i++) {
			if(gas > country[i]) {
				gas = country[i];
				ans += gas*street[i];
			}else {
				ans += gas*street[i];
			}
		}

		System.out.println(ans);
		
		}
	
}

 

 앞서 말했듯이 문제를 정확히 이해 야한다. 나라가 있고 길이 있고 그 길은 일직선 상에 있다. 즉, 따로 최솟값을 찾기 위한 순회는 필요 없다는 의미가 된다.

---

알고리즘 흐름도

입력받기 -> 첫 나라 GAS 가격 초기화 -> 답에 들어갈 최소 가격의 합 초기화 -> 반복을 통한 이후 나라들 가스 가격합 합 구하기 -> 출력하기

---

STEP1 문제 이해하기

 나라마다 정해진 가스 가격이 있고 그 나라에서 다음 나라로 가야 할 거리가 있다. 이점에 주목해야 한다. 우선 입력 예제를 활용해 문제를 이해해 보자

 

주어진 입력이 

4

2 3 1

5 2 4 1

요거라면 어떻게 답을 풀이할 수 있을까?

 

기본적으로 A, B, C, D 나라라고 생각해보자 (각 5, 2, 4, 1의 가스 가격을 가지고 있는)

 

A에서 B로 가기 위해서는 반듯이 5의 가격의 기름을 2번 넣어야 한다. 즉 10이 필요하다.

B에서 C로 가기 위해서는 A와 B 중에서 가장 작은 기름 가격을 넣어서 3을 가야 한다. 즉 B나라에서 3개를 구매하면 된다.

C에서 D로 가기 위해서는 A, B, C 중에서 가장 작은 기름 가격을 넣어서 1을 가야 한다. 즉, B나라에서 1개를 더 구매하면 된다.

 

이해가 되었는가?

 

한 칸씩 이동할 때마다 GAS의 최솟값을 비교해주면 끝이라는 의미이다.

 

이해가 완벽히 되지 않았어도, 이 정도의 이해를 가지고 다음 STEP으로 넘어가 완전한 이해를 도와드립니다.

---

STEP2 gas 및 ans 초기화

 gas의 처음 가격은 A나라 즉 5의 가격을 넣어주면 되고,

 ans의 처음 합은 A나라가 가야 할 거리와 가격을 곱해주면 된다.

long gas = country[0];
ans = country[0]*street[0];

각 country와 street는 성공 코드에서 어떤 값이 들었는지 확인

---

STEP 3 반복 구현하기

 이제 이 구현을 통해서 해당 문제에 대한 완벽한 이해를 도울 수 있다.

		for(int i = 1 ; i < country.length-1 ; i++) {
			if(gas > country[i]) {
				gas = country[i];
				ans += gas*street[i];
			}else {
				ans += gas*street[i];
			}
		}

처음 나라는 이미 들렸으니 1에서부터 전체 나라의-1까지 반복한다.

 

int i = 1인 이유 : 처음 초기화 때 우리는 첫 나라의 값을 이미 초기화해줬기 때문이다.

country.lngth-1인 이유 : 마지막 나라의 gas가격은 굳이 고려하지 않아도 되기 때문이다.

 

if문 : 만약 가스의 최솟값이 다음에 들릴 나라의 가격보다 크다면 ~~

if문의 의미는 A 나라보다 B의 가격이 더 싸다면 이다.

 

gas = country [i]

그렇다면 굳이 A나라의 GAS를 살 필요가 없다. 이에 따라서 앞으로 GAS 구입은 B나라에서 한다.

 

ans += gas*street [i]

그 후 가야 할 거리만 큰 그 가스의 의 곱을 답에 더해준다.

 

els문 : 만약 그 이전의 가스 가격이 더 싸다면

굳이 gas를 변경할 필요가 없으니 그 이전의 최소 가격의 gas로 그 나머지 거리도 충당해라~

 

이런 뜻의 의미로 해석됩니다.

 

입력 예제가 짧으니 아직도 이해가 되지 않으신다면, 대입을 해보시면 됩니다.

 

 * 참고사항으로 이번 주유소 알고리즘에서 대략 58점이 많이 나옵니다.

 그 이유는 바로 마지막 조건인 "원래의 제약 조건 이외에 아무 제약 조건이 없다." 때문입니다.

 

이는 바로 int 말고 long을 사용하란 의미입니다.

 

범위가 1 이상 10억 이하의 숫자임으로 만약 int형을 쓴다면 범위가 넘어갈 수 있기 때문이죠~