백준 13305 (주유소) - java

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

13305번: 주유소

전형적인 DP 문제이다.

• 각 도시의 값들을 city[] 배열에 넣고 거리의 값들을 cost[] 에 넣는다.
• dp[i] 배열의 값은 i번째 지점에서 다음 도시로 이동하는 최소 거리의 값이며 거리에 드는 값은 cost[i] * city[i]를 기본적으로 한다.

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

public class Main {
    static int n = 0;
    static long[]city = new long[100010];
    static long[]cost = new long[100010];

    static long[] dp = new long[100010];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=n-1;i++)
        {
            cost[i] = Long.parseLong(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=n;i++)
        {
            city[i] = Long.parseLong(st.nextToken());
        }

        int idx = 1; // 최소 비용을 가지고 있는 도시의 인덱스
        dp[1] = city[1] * cost[1]; // 첫 번째 도시에서 다음 도시로 가기위해서는 무조건 해당 값

        for(int i=2;i<=n-1;i++)
        {
            if(city[idx] > city[i]) // 최소 비용을 가지고 있는 도시가 나타난 경우
            {
                dp[i] = dp[i-1] + (city[i] * cost[i]);
                idx = i; // 갱신
            }

            else{
                dp[i] = dp[i-1] + (city[idx] * cost[i]);
            }
        }
        System.out.println(dp[n-1]);

        br.close();
    }
}