[백준알고리즘] 그리디 - 13305번 주유소 문제

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

13305번: 주유소

 

간단하게 풀이방식을 설명하자면

현재 위치보다 뒤에 있는 도시중 더 기름값이 싼 도시가 있다면

거기까지의 거리만큼만 기름을 산다

만약 현재 위치의 기름값이 가장 싸고 뒤에 오는 모든 도시들의 기름값이 더 비싸다면

현재 위치에서 마지막 도시까지 갈 만큼의 기름을 모두 사는 식이다

58점을 받았는데 이유는 다루는 값의 범위가 크다보니 int범위 초과 때문이었다

long으로 바꾸면 해결된다

 

풀이코드

package baekjoonWeek6;

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class BJ_13305 {     //백준 주유소 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int cityCnt = Integer.parseInt(br.readLine());  //도시의 개수
        long[] road = new long[cityCnt - 1];  //도시와 도시를 잇는 도로의 거리(비용)
        long[] cost = new long[cityCnt];  //각 도시별 기름값

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < cityCnt - 1; i++) {
            road[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < cityCnt; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }

        int cur = 0;    //어디까지 왔는지 인덱스 표시
        int temp = 1;   //처음으로 cur보다 기름값이 싼 도시의 인덱스
        long tmpDist = 0;    //cur~temp까지의 거리
        long minCost = 0;    //누적되는 기름값, 최소
        while (cur < cityCnt-1) {    //마지막 도시까지 도달할떄까지 구해준다
            while (temp < cityCnt && cost[cur] <= cost[temp]) {   //기름값이 더 싼 도시가 나타날때까지 반복
                temp++;
            }
            for (int i = cur; i < temp; i++) {
                if(i >= cityCnt - 1) break;
                tmpDist += road[i]; //temp까지의 거리를 구한다
            }
            minCost += tmpDist * cost[cur]; //현재 위치의 기름값 * temp까지의 거리를 곱해 비용계산
            cur = temp;
            temp++;
            tmpDist = 0;
        }
        bw.write(Long.toString(minCost));
        bw.flush();
        bw.close();
    }
}