[SWEA] 3820 롤러코스터

출처: [SWEA] SW 문제해결 심화 - 증명의 중요성

 Input 

3

3

3 1

2 2

1 4

5

2 6

1 6

6 3

10 4

7 6

4

1 1

3 2

2 1

2 4

 

 Output 

#1 14

#2 1242

#3 27

 

N개의 레일이 존재하며, 각 레일에는 두 개의 자연수 a, b가 주어져 있다.

[레일의 속도 변화]: (진입 전) v → (진입 후) av + b

※ 롤러코스터가 출발할 때 차량의 속도 = 1

모든 레일을 지났을 때 차량의 속도를 최소한으로 하고자 합니다.

N개의 레일을 적절히 배치하여 최종 속력을 구하시오.

    - Test Case 개수 T / 레일의 개수 N

    - (N줄에 거쳐) 레일에 적힌 수 a, b가 주어집니다.

 

N개의 레일을 배열하는 방법은 O(N!)

배치된 레일을 순회하며 최종속력을 구하는 과정 O(N)

▶ 총 시간복잡도 O(N × N!)

[문제 조건] a와 b는 1000000000 이하의 자연수, 2 ≤ n ≤ 200000 이기때문에 TLE 발생.

 

이 문제의 경우 레일을 재배치하는 과정에서 시간을 확보할 수 있습니다.

정렬 시, Bubble, Heap 등과 같은 정렬 종류에 따라 시간복자도가 다릅니다.

제출 코드에서는 PriorityQueue를 이용해 Heap 구조를 이용했으며, long형 이용.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Solution {
    static final int QUOTIENT = 1000000007;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
             
            PriorityQueue<Rail> pq = new PriorityQueue<>();
            for(int i=1; i<=N; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                pq.add(new Rail(a, b));
            }
             
            long v = 1;
            // 최종속력 계산
            for(int i=1; i<=N; i++) {
                Rail rail = pq.poll();
                v = ((rail.a*v) % QUOTIENT + rail.b) % QUOTIENT;
            }
             
            System.out.println("#" + tc + " " + v);
             
        }
    }
}
 
class Rail implements Comparable<Rail>{
    long a, b;
    Rail(long a, long b){
        this.a = a;
        this.b = b;
    }
     
    @Override
    public int compareTo(Rail target) {
        if((this.b*(target.a-1)) < (target.b*(this.a-1))) {
            return -1;
        }
        else {
            return 1;
        }
    }
}