[백준 - 30094번] 그래서 나는 사진을 그만두었다 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 정렬, 조합론, 수학

입력

첫째 줄에 $N$이 주어진다.

둘째 줄부터 $N + 1$번째 줄까지 $\left( i + 1 \right)$번째 줄에 $c_i$, $a_i$가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 사진 점수의 최솟값과 사진 점수가 최솟값이 되게 줄을 서는 방법의 수를 공백을 사이에 두고 출력한다.

둘째 줄에 사진 점수가 최솟값이 되도록 학생들이 줄을 서는 방법
$x_1, x_2, \cdots, x_N$을 공백을 사이에 두고 출력한다. 쉼표는 출력하지 않는다. 왼쪽으로부터 $i$번째에 학생 $x_i$가 선다는 것을 의미한다. $(1 \le i \le N)$ 

셋째 줄에 사진 점수의 최댓값과 사진 점수가 최댓값이 되게 줄을 서는 방법의 수를 공백을 사이에 두고 출력한다.

넷째 줄에 사진 점수가 최댓값이 되도록 학생들이 줄을 서는 방법
$y_1, y_2, \cdots, y_N$을 공백을 사이에 두고 출력한다. 쉼표는 출력하지 않는다. 왼쪽으로부터 $i$번째에 학생 $y_i$가 선다는 것을 의미한다. $(1 \le i \le N)$ 

줄을 서는 방법의 수는 너무 많을 수 있으니 $998\,244\,353$으로 나눈 나머지를 출력한다.

사진 점수가 최솟값 또는 최댓값이 되게 하는 방법이 여러 가지 있다면, 그중 어떤 것을 출력해도 좋다.

제한

• $1 \le N \le 100\,000$ 
• $-10^8 \le c_i, a_i \le 10^8$ 
• 주어지는 모든 수는 정수이다.

풀이

사진 점수의 최댓값과 최솟값 가능한 경우의 수, 줄을 서는 방법에 대해서 출력해야 한다.

먼저, n이 3일 때 각 자리의 li와 ri를 표시해 보면 (0, 2) (1, 1) (2, 0)이다.

첫 번째 학생이 (1, 0)일 때

첫 번째 자리로 간다면 (0 0 + 2 2)
두 번째 자리로 간다면 (1 0 + 1 2)
세 번재 자리로 간다면 (2 0 + 0 2)
가 된다.

잘 보면, 오른쪽 자리로 갈 수록 c는 한 번 증가하고, a는 한 번 감소하는 것을 알 수 있다.
이를 식으로 정리하면 (c - a)씩 증가한다는 것이고, (c - a)가 가장 큰 값이 가장 오른쪽에 배치하는 것이 최선이 선택이 된다.

그래서 최댓값을 구하기 위해서는 (c - a)를 기준으로 오름차순 정렬하고, 각 인물 점수를 구해서 더해주면 된다.

최솟값 또한 같은 논리로 (c - a)를 기준으로 내림차순 정렬해주고, 계산하면 된다.

그러면 최댓값, 최솟값이 되는 경우의 수는 어떻게 구할까?

만약 인물 점수가 다 다르다면 경우의 수는 1이 된다. 그런데 같은 인물 점수가 존재한다면, 같은 인물 점수끼리 재배치해 줄 수 있기 때문에 여러 경우가 생기며, 이는 순열을 뜻한다. 그래서 같은 개수가 몇개인지 구하고, 팩토리얼로 계산해서 그 값을 다 곱해주면 가능한 경우가 된다.

예를 들어
1 1 1 3 3 4라고 할 때 1은 3개이기 때문에 3!만큼 재배치할 수 있고, 3은 2!만큼 재배치할 수 있다. 1을 배치할 때마다 2!만큼 재배치할 수 있기 때문에 총 경우의 수는 6 * 2로 12가 된다.

이 풀이의 시간 복잡도는 O(N * logN)이다.

소스 코드

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

class Person {
    int v, ind, c, a;
    Person(int ind, int c, int a) {
        this.c = c;
        this.a = a;
        this.ind = ind;
        this.v = c - a;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      StringBuilder sb = new StringBuilder();
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      Person[] arr = new Person[N];
      for(int i=0; i<N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          arr[i] = new Person(i + 1, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
      }
      
      Arrays.sort(arr, new Comparator<Person>() {
         @Override
         public int compare(Person p1, Person p2) {
             return Integer.compare(p2.v, p1.v);
         }
      });
      
      HashMap<Integer, Integer> map = new HashMap<>();
      long min = 0;
      for(int i=0; i<N; i++) {
          if(map.get(arr[i].v) == null) {
              map.put(arr[i].v, 0);
          }
          map.put(arr[i].v, map.get(arr[i].v) + 1);
          min += (long) arr[i].c * i + (long) arr[i].a * (N - (i + 1));
      }
      
      long noc = 1;
      for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
          noc *= factorial(entry.getValue());
          noc %= 998244353;
      }
      
      sb.append(min).append(" ").append(noc).append("\n");
      
      for(int i=0; i<N; i++) {
          sb.append(arr[i].ind).append(" ");
      }
      sb.append("\n");
      
      Arrays.sort(arr, new Comparator<Person>() {
         @Override
         public int compare(Person p1, Person p2) {
             return Integer.compare(p1.v, p2.v);
         }
      });
      long max = 0;
      for(int i=0; i<N; i++) {
          max += (long) arr[i].c * i + (long) arr[i].a * (N - (i + 1));
      }
      
      sb.append(max).append(" ").append(noc).append("\n");
      
      for(int i=0; i<N; i++) {
          sb.append(arr[i].ind).append(" ");
      }
      
      System.out.println(sb.toString().trim());
  }
  
  static long factorial(int n) {
      long result = 1;
      for(int i=2; i<=n; i++) {
         result *= i;
         result %= 998244353;
      }
      return result;
  }
}