[Java] 백준 10713. 기차 여행

📌 문제 링크 - https://www.acmicpc.net/problem/10713

 

---

 

 

 

 

 

 

문제

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 (20점)

• 2 ≦ N ≦ 1 000.
• M = 2.
• 1 ≦ Bi < Ai ≦ 1 000 (1 ≦ i ≦ N − 1).
• 1 ≦ Ci ≦ 1 000 (1 ≦ i ≦ N − 1).

서브태스크 2 (30점)

• 2 ≦ N ≦ 1 000.
• 2 ≦ M ≦ 1 000.
• 1 ≦ Bi < Ai ≦ 1 000 (1 ≦ i ≦ N − 1).
• 1 ≦ Ci ≦ 1 000 (1 ≦ i ≦ N − 1).

서브태스크 3 (50점)

추가적인 제약 조건이 없다.

 

 

• 철도 2와 철도 3의 IC카드를 구입한다. 80+130 = 210원의 비용이 발생한다．
• 1일째에, 도시 1에서 도시 2까지 티켓을 사용해 이동하고, 도시 2에서 도시 3까지는 IC카드를 사용해 이동한다. 120+50= 170원의 비용이 발생한다.
• 2일째에, 도시 3에서 도시 2까지 IC카드를 사용해 이동한다. 50의 비용이 발생한다.
• 3일째에는 도시 2에서 도시 3까지 IC카드를 사용해 이동하고, 다음으로 도시 3에서 도시 4까지 IC카드를 사용해 이동한다. 50+70 = 120원을 사용한다.

이렇게 이동하면, 여행에 드는 비용의 합계는 210+170+50+120 = 550원이 된다. 이 비용이 최소이므로, 550을 출력한다.

 

 

---

 

 

풀이

누적합을 사용해 풀 수 있는 문제다.

도시 방문 경로를 바탕으로 철도 사용 횟수를 계산한 뒤, 각 철도마다 티켓을 쓸지, IC 카드를 쓸지 선택하여 가장 저렴한 비용을 총비용에 더해주면 된다.

 

1. 도시 방문 경로를 입력받으면서 출발역에 +1, 도착역에 -1을 해주며 기록해 준다.  
   번호가 더 작은 도시에 +1, 큰 도시에 -1
2. 1번 기록을 바탕으로 1 ~ N-1 번 철도의 사용 횟수를 구한다.
3. 각 철도마다 티켓을 사용하는 비용 vs IC 카드를 사용하는 비용 중 적은 비용을 총비용에 더해준다.
   티켓 사용 비용 : 티켓 비용 x i 번 철도의 사용 횟수
   카드 사용 비용 : 카드 비용 x i 번 철도의 사용 횟수 + 카드 구매 비용(구매는 한 번만)
4. 총비용 출력

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/10713
public class Main_10713 {
    private static int N, M; // N개의 도시, 여행할 도시의 개수
    private static int[] city; // 방문 횟수
    private static long[] A, B, C; // 티켓 승차 비용, 카드 승차 비용, 카드 구입 비용
    private static long[] lineUse; // 철도 사용 횟수


    public static void main(String[] args) throws IOException {
        init();
        sol();
    }//main


    private static void sol() {
        long totalCost = 0; // 여행에 드는 최저 비용

        // 철도 사용 횟수 구하기
        int sum = 0;
        for(int i=1; i<N; i++) {
            sum += city[i];
            lineUse[i] = sum;
        }

        // 여행에 드는 최저 비용 구하기
        long ticket, card;
        for(int i=1; i<N; i++) {
            ticket = A[i] * lineUse[i];      // 티켓 사용 비용
            card = B[i] * lineUse[i] + C[i]; // 카드 사용 비용
            
            //  -> 티켓 사용 or 카드 구입 중 저렴한 비용 비교 후 계산
            totalCost += Math.min(ticket, card);
        }

        System.out.print(totalCost);
    }//sol


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // N개의 도시
        M = Integer.parseInt(st.nextToken()); // 여행할 도시의 개수

        city = new int[N+1]; // 방문 횟수
        A = new long[N]; // 티켓 승차 비용,
        B = new long[N]; // 카드 승차 비용,
        C = new long[N]; // 카드 구입 비용
        lineUse = new long[N]; // 철도 사용 횟수

        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken()); // 출발
        int e; // 도착
        for(int i=1; i<M; i++) {
            e = Integer.parseInt(st.nextToken());

            if(s < e) {
                city[s]++;
                city[e]--;
            }
            else {
                city[s]--;
                city[e]++;
            }

            s = e;
        }

        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());
        }

        br.close();
    }//init


}//class