[BOJ] 백준 1722. 순열의 순서

▶문제설명

[BOJ] 백준 1722. 순열의 순서

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

▶Hint

---

조합론 & DP 문제이다.

입력으로 주어지는 N의 범위가 최대 20이다.

20! = 2,432,902,008,176,640,000

따라서 브루트포스로 접근할 경우 TLE가 발생하며, 결과 값이 int 자료형 범위를 넘어간다.

문제를 해결함에 있어서 중요하게 봐야 할 조건은 순열이 사전 순으로 정렬되어 있다는 것이다.

이 조건 덕분에 우리는 모든 경우를 확인해보지 않고도 K번째 순열을 찾아내거나 

주어진 순열이 몇 번째 순열인지를 알아낼 수 있다.

N이 4인 경우를 예로 들어보겠다.

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

2 1 3 4

2 1 4 3

2 3 1 4

2 3 4 1

2 4 1 3

2 4 3 1

3 1 2 4

3 1 4 2

3 2 1 4

3 2 4 1

3 4 1 2

3 4 2 1

4 1 2 3

4 1 3 2

4 2 1 3

4 2 3 1

4 3 1 2

4 3 2 1

이렇게 1로 시작되는 경우, 2로 시작되는 경우, 3으로 시작되는 경우, 4로 시작되는 경우의 수가 나온다.

경우의 수들을 적어 놓고 잘 관찰해보면 맨 앞자리 숫자에 따라 각각 6개의 경우가 있다는 것을 알 수 있다.

즉, 길이가 N인 순열에서 앞자리 숫자가 i개 결정되었을 때 각 숫자마다 (N-i)! 개의 경우가 나온다는 것이다.

▶Solution

---

어떻게 하면 K번째 순열을 알아낼 수 있는지 자세히 알아보자.

이 과정을 정확히 이해하고 나서 조금만 응용하면 주어진 순열이 몇 번째 순열인지도 알아낼 수 있을 것이다.

[입력]

4
1 10

입력이 위와 같이 들어왔을 경우

10번째에 위치한 순열을 출력해야한다.

[변수 설명]

N = 순열의 길이
K = 현재 상태에서 몇 번째 순열이 내가 찾는 순열인지

i = 확정된 숫자의 개수 ( 1<= i <= N )

cnt = 앞에서 확정되지 않은 숫자들 중 몇 번째인지 ( 1<= cnt <= N )

[첫 번째 숫자 찾기 - 첫 번째 루프]

N = 4        K = 10        i = 1        cnt = 1

---

cnt는 ( cnt * fac[N-i] >= K ) 조건을 만족하지 않으면 만족할때까지 증가된다.

즉, K가 10이면 cnt가 2일 때 해당 조건을 만족하게 되고, 

처음엔 아무 것도 확정되지 않았으므로 확정되지 않은 숫자들 중 두 번째 숫자는 2가 된다.

10번째 순열의 첫 번째 숫자는 2라고 확정한다. 

그리고 K의 값에서 (cnt-1) * fac[N-i] 만큼을 뺀 값을 K에 저장해준다.

K는 4가 될 것이고, 1로 시작하는 순열의 6가지 경우를 제외시킨다는 것을 의미한다.

[두 번째 숫자 찾기 - 두 번째 루프]

N = 4        K = 4        i = 2        cnt = 1

---

cnt는 ( cnt * fac[N-i] >= K ) 조건을 만족하지 않으면 만족할때까지 증가된다.

K가 4이므로 cnt가 2일 때 해당 조건을 만족하게 되고,

앞에서 숫자 2가 확정된 상태이므로, 확정되지 않은 숫자들 중 두 번째 숫자는 3이 된다.

10번째 순열의 두 번째 숫자는 3이라고 확정한다.

그리고 K의 값에서 (cnt-1) * fac[N-i] 만큼을 뺀 값을 K에 저장해준다.

K는 2가 될 것이고, 1로 시작하는 순열의 2가지 경우를 제외시킨다는 것을 의미한다.

[세 번째 숫자 찾기 - 세 번째 루프]

N = 4        K = 2        i = 3        cnt = 1

---

cnt는 ( cnt * fac[N-i] >= K ) 조건을 만족하지 않으면 만족할때까지 증가된다.

K가 2이므로 cnt가 2일 때 해당 조건을 만족하게 되고,

앞에서 숫자 2, 3이 확정된 상태이므로, 확정되지 않은 숫자들 중 두 번째 숫자는 4가 된다.

10번째 순열의 세 번째 숫자는 4라고 확정한다.

그리고 K의 값에서 (cnt-1) * fac[N-i] 만큼을 뺀 값을 K에 저장해준다.

K는 1이 될 것이고, 1로시작하는 순열의 1가지 경우를 제외시킨다는 것을 의미한다.

[네 번째 숫자 찾기 - 네 번째 루프]

N = 4        K = 1        i = 4        cnt = 1

---

cnt는 ( cnt * fac[N-i] >= K ) 조건을 만족하지 않으면 만족할때까지 증가된다.

K가 1이므로 cnt가 1일 때 해당 조건을 만족하게 되고,

앞에서 숫자 2, 3, 4가 확정된 상태이므로, 확정되지 않은 숫자들 중 첫 번째 숫자는 1이 된다.

10번째 순열의 네 번째 숫자는 1이라고 확정한다.

그리고 K의 값에서 (cnt-1) * fac[N-i] 만큼을 뺀 값을 K에 저장해준다.

K는 1이 될 것이고 4개의 숫자를 모두 확정했으므로 반복문을 빠져나오게 된다.

[출력]

2 3 4 1

[소스 보기]