백준 1722 교재 81 질문

3 asked

2

안녕하세요! 반갑습니다.

순열의 순서 구하기 문제로 이해를 하였는데요.

예제로 한번 말씀드려 보고자합니다.

예를들어 K = 15, 자리수가 4자리라고 가정을 하면 (n=4)

1 2 3 4 중 제일 첫 번째 자리에 어떤 값이 들어가야 하는지 판단하는 경우 K = 15와 (n-1)! = 6을 가지고 비교하게 됩니다. 이유를 생각하여 보면 (n-1)! 이라는 값의 의미는 n자리(여기에서는 제일 앞자리)가 정해졌을 때 나머지 남은 자리로 구할 수 있는 모든 순열의 경우의 수 이기 때문입니다.

해당 문제로 바꾸어 이야기하면 (4-1)! = 6 의 의미는 4자리 순열에서 맨 앞 자리가 정하여 졌을 때 만들 수 있는 경우의 수입니다.

1이 맨 앞자리로 정해졌다고 하면

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

이렇게 6가지 경우의 수가 나옵니다. 그럼 다시 처음으로 돌아가서 K = 15 즉 15번째 순열을 구하는 경우를 생각해보면

1이 가장 앞에 있는 경우 6가지 => K(15) 와 6을 비교하여 K가 더 크면 K에서 6을 마이너스

2가 가장 앞에 있는 경우도 6가지 => K(9)와 6을 비교해서 K가 더 크면 K에서 6을 마이너스

3이 가장 앞에 있는 경우도 6자기 => K(3)과 6을 비교하면 6이 더 크기 때문에 15번째 순열은 제일 앞자리가 3으로 시작함.

즉

1~6번째 순열까지는 제일 앞자리에 1이 있는 순열이고

7~12번째 순열이면 제일 앞자리에 2가 있는 순열이고

13~18번째가 제일 앞자리에 3이 있는 순열이기 때문에

15번째 순열은 제일 앞자리에 3이 온다는 것을 알 수 있습니다.

더불어 여기에서 앞에 12번째 순열의 개수가 마이너스가 되었기 때문에

K = 15 번째 순열은 제일 앞자리가 3이면서

3 X X X 로 만들 수 있는 순열 중 3번째 ( 15 -12 ) 순열이라는 것을 파악 할 수 있습니다.

때문에 이러한 원리로 K번째 순열 출력할때, k와 (n-1)! 을 비교하여 보는 것이라고 이해해주시면 좋을 것 같습니다.

감사합니다.

즐거운 주말 되세요.