[백준] 10713. 기차 여행

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

 

• 가격 비교  (min(a * k, c + b * k)) 
  • 각 철도를 이용하는 총 횟수를 알아내고, 그에 따라 해당 철도를 이용할 때 티켓을 구매하는 방법과 IC 카드를 구매하는 방법 중 가격이 더 작은 방법을 이용하면 된다.
• 철도 이용 횟수 구하기 (누적합)
  • 각 철도를 이용하는 횟수를 구해야 하는데, 만약 도시 1번에서 3번으로 이동할 경우, 1번 철도와 2번 철도를 이용한다. 그런데 이런 식으로 카운트하면, 이동 횟수가 m번이고 매 이동마다 가장 먼 도시로 이동한다고 가정했을 때 O(m * n)의 시간 복잡도가 소요되어 시간초과가 날 수 있다.
  • 따라서 누적합을 이용해야 한다. 누적합 활용 방식은 다음과 같다.
    • 도시 1번에서 5번으로 이동한다고 가정하자.
    • 누적합을 사용하지 않으면 1번 철도부터 4번 철도까지 이용하므로, p[1]++, p[2]++, ... , p[4]++을 해줘야 한다. (이는 시간 초과!)
    • 반면, 누적합을 사용하면, 1번 철도를 이용한다는 의미로 p[1]++만 해준다. 그리고 2번 철도 이용 횟수는 누적합을 이용해서 p[1]의 값을 누적합을 해주면 되고, 이러한 누적합은 p[5]부터는 끝내야 하므로 p[5]--을 해주면 된다.
    • 말로 설명하니 어려운데, 직접 적어보면 좀 더 와닿을 수 있다.
      • 1번 도시에서 5번 도시로 이동 = 1, 2, 3, 4번 철도 이용
      • p[1]++, p[5]-- ➡️ 배열 p는 (인덱스 1부터 5까지) 1, 0, 0, 0, -1가 된다.
      • 따라서 이를 누적합 해주면 1, 1, 1, 1, 0이 되고, 이는 각 철도의 이용 횟수가 된다.
  • 즉, 누적합을 이용함으로써 각 철도 이용 횟수를 구할 때, O(N*M) 에서 O(N + M)으로 줄일 수 있다. (이렇게 일정 범위을 하나씩 이동하며 순차 탐색하는데 시간 초과가 우려되면 누적합을 고려해보자!)

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n; // 도시의 수
    static int m; // 여행 기간

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 경로 입력받기
        int[] routes = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            routes[i] = Integer.parseInt(st.nextToken());
        }

        // 철도 이용 금액 입력받기 (1번 철도 ~ n - 1번 철도)
        int[][] price = new int[n][3];
        for (int i = 1; i <= n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            price[i][0] = Integer.parseInt(st.nextToken()); // 티켓 금액
            price[i][1] = Integer.parseInt(st.nextToken()); // 카드 금액
            price[i][2] = Integer.parseInt(st.nextToken()); // 카드 구매 금액
        }

        // 누적합을 위한 배열 p 생성
        int[] p = new int[n + 1];
        for (int i = 0; i < m - 1; i++) {
            int start = routes[i];
            int end = routes[i + 1];
            if (start < end) {
                p[start]++;
                p[end]--;
            } else {
                p[end]++;
                p[start]--;
            }
        }

        // 1번 ~ n - 1번 철도의 이용 횟수 구하기 (누적합) + 총 비용 구하기
        int totalPrice = 0;
        int psum = 0;
        for (int i = 1; i < n; i++) {
            psum += p[i]; // psum: i번 철도를 이용하는 횟수
            totalPrice += Math.min(price[i][0] * psum, price[i][2] + price[i][1] * psum);
        }

        System.out.println(totalPrice);
    }
}