[코딩테스트] Java_ 백준 13305번 주유소 (그리디 알고리즘) - Rowen Jobs

백준 13305번 주유소

초기 접근을 잘 해야 시간 낭비를 하지 않는다는걸 꺠달은 문제였다. 

 

왼쪽에서 오른쪽으로 갈때 주유비 최소 금액을 구하는 문제였고 프로세스는 아래와 같다.

(예시) 도시 사이 거리 [2, 3, 1], 각 도시 리터 가격 [5, 2, 4, 1]

1.  각 도시 리터 가격 첫번째인 5로 시작한다.

2. 첫번째 도시에서 두번째 도시를 갈때 무조건 기름을 채워야 가기에 첫번째 도시에서 두번째 도시의 기름값을 total 에 더해준다(5 * 2)

3. 그 후 --> 첫번째 도시와 두번째 거리(5, 3) 두번째 도시와 두번째 거리(2, 3) 의 값을 비교하여 적은 값을 total 에 더해준다.(15 > 6)

4. 두번째 도시가 리터 가격(2, 3)이 적기 때문에 첫번째 도시에서 두번째 도시로 기준으로 변경한다.(만약 두번째 도시가 적을 경우는 첫번째 도시가 계속 기준이 되어 첫번째 도시 * 세번째 거리, 세번째 도시 * 세번째 거리 형태로 진행이 된다.)

5. 두번째 도시와 세번째 거리, 세번째 도시와 세번째 거리 비교를 하여 적은 기름값을 total 에 더해준다. (2 < 4)

6. 마지막 도시는 비교리스트에서 제외해버린다. 

7. 그렇게 되면 10 + 6 + 2 가 되어 18이 된다.

 

주유소 성공서브태스크

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

56611

21887

17138

38.281%

문제

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

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

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

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 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	41	2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.
3	42	원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1 복사

4
2 3 1
5 2 4 1

예제 출력 1 복사

18

예제 입력 2 복사

4
3 3 4
1 1 1 1

예제 출력 2 복사

10

출처

Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 2번

알고리즘 분류

• 그리디 알고리즘

채점 및 기타 정보

• 예제는 채점하지 않는다.

주석과 함께 코드는 아래와 같다.

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        // 도시 갯수 셋팅
        int city_qty = Integer.parseInt(st.nextToken());
        
        // 도시 간 거리 배열 
        long[] km_btw_city = new long[city_qty - 1];
        // 도시 간 거리 구간합 배열
        long[] km_btw_city_sum = new long[city_qty - 1];
        // 각 도시 리터당 기름값 배열
        long[] oil_amt = new long[city_qty];
		
        // 도시 간 거리 배열 셋팅
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < city_qty - 1; i++){
            km_btw_city[i] = Long.parseLong(st.nextToken());
            // 구간합 배열 셋팅(반복문을 돌리지 않고 남은 거리를 바로 계산하기 위함.)
            if(i == 0){
                km_btw_city_sum[i] = km_btw_city[i];
            }else{
                km_btw_city_sum[i] = km_btw_city[i] + km_btw_city_sum[i - 1];
            }
        }
		
        // 각 도시 리터당 가격 배열 셋팅
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < city_qty; i++){
            oil_amt[i] = Long.parseLong(st.nextToken());
        }
        // 이동 간 기름값 최소 가격 변수 선언 
        long total = 0;
        
        // 최소 가격 셋팅
        for(int i = 0; i < city_qty - 1; i++){
        	// 첫번째 도시 * 첫번째 거리에서만 total 값 셋팅(기름을 넣냐 안넣냐 선택이 아니라 필수)
            if(i == 0){
                total += oil_amt[i] * km_btw_city[i];
            }
            // 위 설명 3, 4번에 해당, 하나의 도시가 기준이 되어 앞으로 남은 거리에 대한 계산
            for(int j = i + 1; j < city_qty - 1; j++){
            	// 설명 3번 참고, 하나의 도시의 리터 * 거리 가격과 그 다음에 있는 도시의 리터 * 거리 가격 비교
                if((oil_amt[i] * km_btw_city[j]) < (oil_amt[j] * km_btw_city[j])){
                	// 기준이 되는 도시가 적을 경우 total만
                    total += oil_amt[i] * km_btw_city[j];
                    // 만약 비교 거리가 마지막이라면 해당 거리에 맞는 도시 값 셋팅(마지막 단계)
                    if(j == city_qty -2){
                        i = (j - 1);
                    }
                }else{
                	// 기준이 되는 도시가 더 클 경우 total에 적용 후 기준이 되는 도시를 변경
                    total += oil_amt[j] * km_btw_city[j];
                    i = (j - 1);
                    // 변경 처리 후 더 이상 기준이 되었던 도시로 거리 * 리터 비교가 필요 없기에 break 처리
                    break;
                }
            }
        }
        System.out.println(total);
    }
}

이미지로 부가 설명 

1. 첫번째 도시  -> 두번째 도시 : 10원 추가

2. 첫번째 도시 3km에 대한 리터당 가격, 두번째 도시 3km에 대한 리터당 가격 비교 

3. 15(첫번째 도시) 와 6(두번재 도시) 중 6원이 더 저렴하므로 두번째 도시에서 기름을 추가로 넣는걸로 함.(코드상에서는 기준 도시 변경 후 break 처리)

4. 두번째 1km에 대한 리터당 가격, 세번째 도시 1km에 대한 리터당 가격 비교

5. 2(두번째도시) 와 4(세번째도시) 중 2원이 더 저렴하므로 세번째 도시에서 주유하지 않고 두번째 도시에서 1km 에 대한 기름을 넣고 감. 

6. 네번째 도시는 마지막 도착하는 도시라 비교할 필요가 없음.(코드상에서 도시갯수 - 1 반복문 처리와 같음)