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

🔺 문제

13305번: 주유소

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        long[] km = new long[n - 1]; // 도시 간 거리
        long[] price = new long[n]; // 기름값
        
        // 도로 길이 저장
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < km.length ; i++) {
            km[i] = Long.parseLong(st.nextToken());
        }
        
        // 주유 가격 저장
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < price.length ; i++) {
            price[i] = Long.parseLong(st.nextToken());
        }
        
        long sum = 0;
        long min = price[0]; // 이전까지 과정 중 최솟값
        
        for(int i = 0 ; i < km.length ; i++) { // 마지막 주유소 가격은 고려 X.
            // 첫 도시 vs 다음 도시 주유 가격 비교해 더 낮은 주유 가격만큼 주유
            if(price[i] < min) {
                min = price[i];
            }
            
            sum += (min * km[i]);
        }
        
        System.out.println(sum);
    }
}

✅ 해결 아이디어
✔ 그리디
- 리터 당 기름값이 '내림차순'일 경우 주유
 → 첫 도시 vs 다음 도시의 주유 가격 비교해, 더 낮은 주유 가격만큼 주유 (= 최솟값 주유)

 

💥 유의사항

• long형으로 받기⇨ 입력값이 10억까지 들어올 수 있어, in형 범위 넘음.

 

 

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

주유주유... 글씨 계속 보니까 게슈탈트 붕괴 현상 왔다...

주유해주유...

 

암튼 다음엔 스스로 생각해내서 빨리 풀어보자,,,

 

1회독	2회독	3회독	4회독	5회독
V	240416

---

(참고)

- 풀이 참고

[JAVA] 백준 13305 - 주유소

[백준] 자바 Java, 13305번: 그리디 알고리즘 > 주유소

 

[백준] 13305번 : 주유소 - JAVA [자바]