[BaekJoon] G5 1722 순열의 순서

Math . ..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

1. 문제

1722번: 순열의 순서

 

 

 

---

2. 이해

아이디어를 떠올리기 어려운 문제였다. 

 

 

[소문제 번호 1]

예를 들어 N = 5 라고 생각하자.

그렇다면 배열은 1, 2, 3, 4, 5로 이루어져 있을 것이다.

k = 67이라고 해보자. (67번째 순서의 배열을 구해야 한다.)

 

먼저 그 배열의 첫번째 숫자를 하나씩 고정해보자.

[1, ?, ?, ?, ?] => 이 경우는 4! = 4*3*2*1 = 24가지이다.

[2, ?, ?, ?, ?] => 4! = 24

...

 

67에서 24를 빼면서 첫번째 숫자를 다음 번호로 넘기면 된다.

 

67 - 24 = 43 => 첫 번째 자리는 1보다 크다.

43 - 24 = 19 => 첫 번째 자리는 2보다 크다

19 - 24 = -5 < 0 => 첫 번째 자리는 3이다.

 

따라서 첫 번째 자리의 숫자는 3 확정이다.

 

그렇다면 남은 배열은 [3, ?, ?, ?, ?] 의 형태일 것이다. (3 고정, ?에는 3이 포함되어 있지 않다.)

 

배열의 두 번째 숫자를 하나씩 고정해보자.

[3, 1, ?, ?, ?] => 3! = 3*2*1 = 6가지

[3, 2, ?, ?, ?] => 3! = 6

...

 

67 - 24 - 24 = 19였다.

 

따라서 

19 - 6 = 13 => 두 번째 자리는 1보다 크다

13 - 6 = 7 => 두 번째 자리는 2보다 크다

7 - 6 = 1 => 두 번째 자리는 4보다 크다

1 - 6 = -5 < 0 => 두 번째 자리는 5다.

 

따라서 현재까지 확정된 배열은 [3, 5, ?, ?, ?] 의 형태일 것이다. (3, 5 고정, ?에는 3, 5가 포함되어 있지 않다.)

 

이런 식으로 모든 자리가 정해질 때 까지 반복한다.

 

[소문제 번호 2]

N = 5일 때, 만약 주어진 수열이 [3, 5, 1, 2, 4] 일 때 k 값을 구해야 한다. (몇 번째 수열인지?)

 

첫 번째 자리가 3으로 만약 고정한다 치면 첫 번째  자리가 1일때, 2일때 다음번이므로, 

k는 기본적으로 4! + 4! = 48 보다 크다.

 

두 번째 자리를 5로 고정한다면, 앞의 1 / 2 / 4 다음 순서이므로, 

3! * 3 = 18 => 48 + 18 = 66보다 크다.

 

이런식으로 모든 자리가 정해질 때 까지 반복한다.

 

 

[자료형]

이 문제에서는 Factorial이 계산에 자주 사용되기 때문에, 처음 부터 Factorial 배열에 (1<=N<=20) 만큼 저장해둔다.

그런데 20! 은 2,432,902,008,176,640,000 으로, long 자료형을 사용해야 한다. 

그리고 당연하게도 20! 정도의 값이 들어가므로 노가다로 구하려 한다면 무조건 2초를 초과할 것이다.

 

 

---

3. 전체 코드

/*
* Memory : 11556 KB
* Time : 80 ms
* */

package BaekJoon.Gold;

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

public class G5_1722_순열의_순서 {

    private static int N;
    private static long k;
    private static int type;

    private static boolean[] visited;
    private static long[] factorial;
    private static int[] arr;

    private static List<Integer> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        factorial = new long[21];
        factorial[0] = 1;

        for(int i=1; i<=20; i++)
            factorial[i] = i * factorial[i-1];

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N+1];
        arr = new int[N+1];
        list = new ArrayList<>();

        st = new StringTokenizer(br.readLine(), " ");

        type = Integer.parseInt(st.nextToken());

        if(type == 1) {
            k = Long.parseLong(st.nextToken());

            for(int i=0; i<N; i++) {
                for(int j=1; j<=N; j++) {
                    if(visited[j])
                        continue;

                    if(k - factorial[N-1-i] > 0)
                        k -= factorial[N-1-i];
                    else {
                        list.add(j);
                        visited[j] = true;
                        break;
                    }
                }
            }

            for (Integer i : list)
                System.out.print(i + " ");
        }
        else {
            long partSum = 1;

            for(int i=0; i<N; i++)
                arr[i] = Integer.parseInt(st.nextToken());

            for(int i=0; i<N; i++) {
                for(int j=1; j<arr[i]; j++) {
                    if(!visited[j])
                        partSum += factorial[N-i-1];
                }

                visited[arr[i]] = true;
            }

            System.out.println(partSum);
        }
    }
}

 

---

4. 생각

이 문제가 왜 G5인지 잘 모르겠다. 어렵다. 

 

이런 수학 관련 문제나, 특정 아이디어를 떠올리지 않으면 풀기 어려운 문제는 진짜 쉽지 않다.