[백준] 13305번: 주유소 자바(Java)

문제

---

13305번: 주유소

접근법

---

리터당 가격이 가장 낮은 곳에서 최대한 많은 양의 기름을 채워야 한다.

즉 리터당 기름 값이 ‘내림차순’일 경우에만 주유한다!!

설명하기 쉽게 각 나라의 리터당 가격을 p라고 하겠다.

순차적으로 왼쪽에서 오른쪽 나라로 이동한다고 한다고 가정하자.

첫 나라에서 p를 읽어들이고 다음 나라로 순차적으로 이동 이동

• 다음 p가 크거나 같으면 패스
• 다음 p가 더 작다면 지금까지 온 모든 거리의 합에 가장 최근에 읽은 p를 곱한다.

• 그렇다면 그림의 체크와 같이 5, 2, 1 점점 작아지는 p만 선택해서 계산에 참여하게 된다.

풀이

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    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 N = Integer.parseInt(br.readLine());

        StringTokenizer l = new StringTokenizer(br.readLine()); //각 나라 사이 거리
        StringTokenizer p = new StringTokenizer(br.readLine()); //각 나라의 리터당 가격
        int price = Integer.parseInt(p.nextToken());

        int min_price = 0;  // 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용
        int length_sum = 0; // 지금까지 왔던 거리 저장하는 변수

        while (p.hasMoreTokens()) { //왼쪽에서 오른쪽으로 나라 이동
            length_sum += Integer.parseInt(l.nextToken());
            int nextPrice = Integer.parseInt(p.nextToken());

            if (nextPrice <= price) { //다음 나라의 리터당 가격이 더 작을 경우 -> (지금까지 왔던 거리 * 현재 price)
                min_price += length_sum * price;

                length_sum = 0;
                price = nextPrice;
            }

        }

        bw.write(String.valueOf(min_price));
        bw.flush();
    }
}

• 실행결과를 보니 부분성공했다.. 왜지?
  1. N의 범위가 매우 큰데 Long 사용 안함
  2. 맨 끝에서 ‘내림차순’이 아니라면 아예 거리가 계산되어서 min_price에 들어가지 않는다.
• ex)

7
2 3 5 1 4 2
5 3 7 4 6 1 2

출력 결과: 49 
-> 마지막 나라가 내림차순이 아니므로 if문안으로 들어가지 않아서 거리가 계산이 안되었음

⇒ if문 안에서의 동작을 줄이자!!

• if문안에서는 현재 계산하려는 최소 리터당 기름값만 갱신
• if문 밖에서는 항상 더해지는 로직을 구현

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    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 N = Integer.parseInt(br.readLine());

        StringTokenizer l = new StringTokenizer(br.readLine()); //각 나라 사이 거리
        StringTokenizer p = new StringTokenizer(br.readLine()); //각 나라의 리터당 가격
        long price = Long.parseLong(p.nextToken());

        long min_price = 0;  // 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용
        long distance; // 나라 사이 거리 저장

        while (p.hasMoreTokens()) { //왼쪽에서 오른쪽으로 나라 이동
            distance = Long.parseLong(l.nextToken());
            long nextPrice = Long.parseLong(p.nextToken());

            min_price += distance * price;

            if (nextPrice < price) { //다음 나라의 리터당 가격이 더 작을 경우 -> price 갱신
                price = nextPrice;
            }

        }

        bw.write(String.valueOf(min_price));
        bw.flush();
    }
}