[백준13305:주유소][JAVA]

Boknami·2023년 9월 24일

백준문제풀이

목록 보기

39/45

💡 첫 아이디어

/*
        가장 오른쪽 도시까지 가기 위한 최소 비용
        - 현재 기준 오른쪽 도시에 가기 위한 km
        - 현 가격 vs 다음 도시 가격 측정

        => 현재 가격이 다다다다다음꺼보다도 더 쌀 수도 있다!
        => 즉 한 번의 측정이 이~~~~후에 영향을 미칠 가능성!
*/

처음에 코드를 작성하기 전에 주석으로 미리 흐름을 생각해본 내용이다!
=>부분은 한 번 돌리고 실패한 후 추가로 적은 내용!

가장 오른쪽 도시를 가기 위해서는 이동하기 전에 미리 현재 주유소가 비싼 지 아님 다음 주유소가 비싼 지를 비교하고 움직이려고 코드를 짰다!

🚨문제점

그런데 여기서 문제가 발생했다.

당장에 예시 문제들을 다 정답이 나왔으나, 실제 채점은 서브태스크1인 17점 밖에 얻지 못했다. 그 이유는 위 그림과 예시처럼 현재 주유소 vs 다음 주유소의 가격만 고려하면 예시는 통과 가능하나..아래 그림과 같은 상황에서는 최적을 고를 수 없다!

위 그림처럼 아직까지 남아있는 주유소들의 어떤 가격과 비교해도 가장 저렴한 곳이 있다면 굳이 다른 곳을 생각할 수가 없다..예를 들어 진짜 최저가로 파는 집이 있으면 거기서 다 사지 다른 곳을 알아볼 필요가 없는 것이다!!

🤔수정 후 도전..그러나

수정 후 나름 완벽하다 자신을 하고 돌렸는데 58점..아마 서브태스크의 한 개를 놓친 것 같았다.

2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.

이 부분을 놓친 것 같았는데 솔직히 무슨 말인지 무얼 뜻하는지 잘 이해가 안되었다. 뭐야 그냥 거리가 늘어나고 가격이 더 늘어난다는 거 아니야? 싶었는데..

👍 정답 도달 및 코드

해당 서브태스크는 값이 엄청 커질 수 있으니 너 그것도 고려해봐! 라는 의미였다..그것을 위해서 커지는 가격을 받아내기 위해 int를 Long타입으로 바꿨더니 100점!!

import java.io.*;
import java.util.*;

public class Main {
    /*
        가장 오른쪽 도시까지 가기 위한 최소 비용
        - 현재 기준 오른쪽 도시에 가기 위한 km
        - 현 가격 vs 다음 도시 가격 측정

        => 현재 가격이 다다다다다음꺼보다도 더 쌀 수도 있다!
        => 즉 한 번의 측정이 이~~~~후에 영향을 미칠 가능성!
    */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int cityNum = Integer.parseInt(st.nextToken());
        int[] distance = new int[cityNum-1];
        int[] literPrice = new int[cityNum];

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

        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < cityNum; i++){
            literPrice[i] = Integer.parseInt(st.nextToken());
        }

        long price = 0;
        int i = 0;
        long curResonablePrice = literPrice[0];
        while(true){
            if(i == cityNum-1) break;

            if(curResonablePrice >= literPrice[i+1]){
                //현재 가격이 더 높아서(비효율) 일단 다음 곳까지만 주유하고 가자!
                price += curResonablePrice * distance[i];
                curResonablePrice = literPrice[i+1];
                i++;
            }
            else{
                //현재 가격이 더 낮다 => curResonable유지
                price += curResonablePrice * distance[i];
                i++;
            }
        }
        System.out.println(price);
    }
}