[ BOJ ][JAVA][10713] 기차 여행

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	961	398	279	42.401%

문제

JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다.

그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다.

철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다.

JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다.

• 철도 i에 티켓을 구입해 승차할 때는 Ai 원의 비용이 든다.
• 철도 i에 IC카드로 승차하는 경우에는 Bi 원의 비용이 든다. 하지만 IC카드로 철도를 탈 때는 IC카드를 미리 구입해둬야만 한다. 철도 i에서 쓸 수 있는 IC카드를 구입하는데는 Ci원의 비용이 든다. 한번 구입한 IC카드는 몇번이라도 사용할 수 있다.

IC카드가 처리가 간편하기 때문에, IC카드로 승차하는 방법의 운임이 티켓을 구입하는 경우보다 싸다. 즉, i = 1,2,...N-1일 때 Ai > Bi이다. IC카드는 철도마다 다르기 때문에, 철도 i에서 사용할 수 있는 카드는 다른 철도에서는 사용할 수 없다.

당신은 JOI나라를 여행하기로 마음먹었다. 도시 P1에서 출발해, P2,P3... ,PM 순서의 도시를 방문할 예정이다. 여행은 M-1일간 이루어진다. j일째 (1 ≦ j ≦ M − 1) 에 도시 Pj으로부터 Pj+1으로 이동한다. 이때, 여러 개의 철도를 타는 경우도 있고, 같은 도시를 여러 번 방문할 수도 있다. JOI나라의 철도는 빨라서 어느 도시도 하루만에 도착할 수 있다

당신은 현재 어느 철도의 IC카드도 갖고있지 않다. 당신은 미리 몇개의 IC카드를 구입해, 이 여행에서 사용되는 비용, 즉 IC카드를 구입하는 비용 + 철도를 타는 비용을 최소화하고 싶다.

JOI나라의 도시 수, 여행의 기간, 그리고 JOI나라의 철도 각각의 운임과, IC카드의 가격이 주어졌을 때, 여행의 비용을 최소화하는 프로그램을 작성하시오.

입력

첫 번째 줄에서는 정수 N, M이 주어진다.

두 번째 줄에는 M개의 정수 P1,P2,...PM이 주어진다. j일째 (1 ≦ j ≦ M − 1) 에 도시 Pj에서 Pj+1로 이동하는 것을 의미한다.

3번째 줄부터 N-1개의 줄에는 (1 ≦ i ≦ N − 1) 3개의 정수 Ai, Bi, Ci가 주어진다. 각각 철도 i의 티켓을 구입하는 가격, 철도 i를 카드를 사용했을 때 통과하는 가격, IC카드를 구매하는 가격을 의미한다.

출력

여행에 드는 최저 비용을 첫째 줄에 출력하시오.

제한

• 2 ≦ N ≦ 100 000．
• 2 ≦ M ≦ 100 000．
• 1 ≦ Bi < Ai ≦ 100 000 (1 ≦ i ≦ N − 1)．
• 1 ≦ Ci ≦ 100 000 (1 ≦ i ≦ N − 1)．
• 1 ≦ Pj ≦ N (1 ≦ j ≦ M)．
• Pj ≠ Pj+1 (1 ≦ j ≦ M − 1)．

예제 입력 1

4 4
1 3 2 4
120 90 100
110 50 80
250 70 130

예제 출력 1

550

예제 입력 2

8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3

예제 출력 2

81

코드

누적합 풀이

손익분기점과 같이 ak 와 bk + c 중 최소를 찾으면된다.
도로를 지나는 횟수인 k를 구하는 것이 누적합 풀이 핵심

/*
    기차 여행
    누적합 or Segment Tree (Lazy Propagation)
*/
import java.io.*;
import java.util.*;
public class p10713 {
    static int n, m;
    static int[] a, b, c, d, p;
    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());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        a = new int[n + 1];
        b = new int[n + 1];
        c = new int[n + 1];
        p = new int[n + 1];
        d = new int[n + 1];

        // 여행 순서
        for (int i = 1; i <= m; i++) {
            p[i] = Integer.parseInt(st.nextToken());
        }

        // 도시번호 1 2 3 4
        // 방문횟수 +   -
        // 방문횟수   + -
        // 방문횟수   +   -
        for (int i = 2; i <= m; i++) {
            int prev = p[i - 1]; // 1, 3, 2
            int next = p[i]; // 3, 2, 4

            if (prev > next) {
                int tmp = prev;
                prev = next;
                next = tmp;
            }
            // 방문횟수
            d[prev]++; // 이 철도부터는 방문 횟수가 1 늘어난다.
            d[next]--; // 이 철도부터는 방문 횟수가 1 줄어든다.
        }

        // 철도
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
            c[i] = Integer.parseInt(st.nextToken());
        }

        long result = 0, psum = 0;
        for (int i = 1; i < n; i++) {
            psum += d[i];
            //System.out.println(i+"번째 철도의 d[i]:"+d[i]+", 방문횟수(psum):"+psum);
            result += Math.min(psum * a[i], psum * b[i] + c[i]);
        }
        System.out.println(result);
    }
}

Lazy Propagation 풀이

// 업로드 예정