백준 자바 문제풀이 #13305

문제 링크

주유소

여러 주유소를 거치며 목적지까지 도달하는 최소비용을 구하는 문제다.

이번 문제는 백준의 "단계별로 풀어보기"에서

그리디 알고리즘을 선택한, 문제의 유형을 알고 푸는 문제다.

...근데 그리디 알고리즘이 딱히 파훼법이 없는 스타일이라

문제유형을 몰랐어도 풀이가 크게 달라지진 않았을것이다.

예제를 먼저 보자.

원에 들어있는 수는 해당 지점에서 주유 시 요구하는 리터 당 비용이다.

도로 위의 숫자는 거리다.

연비는 거리 당 1리터 이다.

풀이과정

처음에는 모든 경우를 구해서 그 최솟값을 취하려고 했는데

그러기엔 너무 시간소요가 많이 걸릴것 같았다.

다이나믹 프로그래밍 방식으로 풀어보련다.

첫번째 지점은 출발지점이니 dp[0] = 0;

두번째 지점에 가려면 첫번째 지점에서 기름을 넣을 수 밖에 없다.

dp[1] = 5 * 2 = 10;

세번째 지점에 가려면 두번째 지점에서 보다 저렴한 기름을 넣어야 한다.

dp[2] = 2 * 3 = 6;

네번째 지점에 가려면 세번째 지점에서 주유하는것보다

두번째 지점에서 주유하는것이 더 저렴하다.

dp[3] = 2 * 1 = 2;

따라서 총 경비 18이다.

문제 풀이과정을 되짚어 봤을때 이번 문제의 핵심은

리터당 기름가격이 내림차순이 되어야 함

이다.

코드를 짜봤다.

코드(중간점수)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] dist = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            dist[i] = Long.parseLong(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        long[] cost = new long[n];
        long[] tmp = new long[n];
        long max = 10_000L;
        for (int i = 0; i < n; i++) {
            cost[i] = Long.parseLong(st.nextToken());
            if (max > cost[i]) {
                max = cost[i];
            }
            tmp[i] = max;
        }

        // 메인 알고리즘
        long[] dp = new long[n];
        dp[1] = cost[0] * dist[0];

        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + tmp[i - 1] * dist[i - 1];
        }

        System.out.println(dp[n - 1]);
    }
}

나름 잘 짠 것 같은데...

중간점수가 나왔다. 58점. 자바 11 33116 KB 356 ms

어느 부분에서 놓쳤는지 감이 안잡힌다.

---

결국 잘못된 점을 찾지 못해서 질문게시판에 질문을 등록해 놓은 상태다.

다른 사람들의 풀이를 보니... 접근방식은 비슷한데

DP가 아니라 그리드로 풀었다는 차이...?

풀이가 이해가 안되는건 아닌데

효율성 차이 때문인지 아니면 잘못된 부분이 있는지는 모르겠다.

코드(만점)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] dist = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            dist[i] = Long.parseLong(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        long[] cost = new long[n];
        for (int i = 0; i < n; i++) {
            cost[i] = Long.parseLong(st.nextToken());
        }

        // 메인 알고리즘

        long total = cost[0] * dist[0];
        long minCost = cost[0];
        for (int i = 1; i < n - 1; i++) {
            if (minCost > cost[i]) {
                minCost = cost[i];
            }

            total += minCost * dist[i];
        }

        System.out.println(total);
    }
}

자바 11 35788 KB 444 ms

개운하지가 못하다.