[PS] 백준13305 : 주유소(Java)

문제

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

 

---

풀이

현재 주유소(i)와 다음 주유소(j)의 가격을 비교하여 현재 주유소가 저렴할 경우 다음 거리까지 주유.

만약 다음 주유소가 저렴할 경우 현재 주유소에서 다음 주유소까지의 거리만큼만 주유.

---

소스코드

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

//BOJ_13305
public class Main {
    static int cityCnt;
    static int[] dist, store;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        cityCnt = Integer.parseInt(br.readLine());
        dist = new int[cityCnt-1];
        store = new int[cityCnt];

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

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

        long res = 0;

        for(int i=0; i<store.length-1; i++) {
            int curCost = store[i];
            res += (long) dist[i] * curCost;
            //현재 지점보다 저렴한지점까지 탐색
            for(int j=i+1; j<store.length-1; j++) {
                if(j == store.length-1) break;

                if(curCost <= store[j]) {
                    res += (long) dist[j] * curCost;
                    i++;
                }
                else break;
            }
        }

        System.out.println(res);

    }
}

---

반례

5
2 1 2 6 
8 8 6 9 8 
---
ans : 72

---

정리

그리디 알고리즘들이 접근법을 떠올리지 못하면 말리게하는 분류중에 하나인 것 같습니다. 최근 코딩테스트에도 그리디 문제들이 종종 출제되는 걸 보아서 많이 풀어보는게 좋을 것 같아서 시도했던 문제입니다. 또 생각해보면 현재 좌표를 기준으로 다음의 값들을 비교하는 과정을 자주 봤던 것 같아요.

 

이런 구현 문제에서 2중 for문을 작성하다보면 가끔 뭘 구현하려 했는지 헷갈릴 때가 있는데, 변수 네이밍 또는 로직에 대해서 간단히 주석을 추가하면서 작성하는 습관을 들여야 할 것 같습니다.

 

혹시 코드를 작성하다가 헷갈리거나 생각이 나지 않는 경우를 예방할 수 있는 좋은 방법이 있다면 추가로 포스팅을 올리도록 하겠습니다!