[platinum5][해설분류 미확인] 1413 박스안의 열쇠

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

 

 

오랜만에 풀어보는 매콤한 조합론 문제였다.

처음엔 나중에 알게된 개념이지만 교란수열과 똑같이 점화식을 구현해보았지만... 사이클이 여러개 발생해서 오답을 받았다.

처음엔 이렇게 박스와 열쇠 번호가 같은 경우엔 반드시 폭탄이 한개씩 필요하고,  그외 4567 번 박스와 같은 경우에는 폭탄을 한번만 아무곳이나 터트리면 아래와 같이 연쇄적으로 박스를 열 수 있다. 따라서 열쇠는 4개가 필요하다.

이런식으로 D[n] 은 한쌍도 박스와 열쇠번호가 같지 않은 쌍 번호로 치고, 점화식으로 나타낼 수 있었다. ( 여기서는 D[4])

 

(fact : 팩토리얼, C[i][j] : i C j)

 

그러나 이것은 잘못된 생각이었다.

다음과 같은경우 열쇠 박스 번호가 같은 경우는 없지만 2개의 사이클이 생긴다... 결국 폭탄이 1개가 아닌 2개가 필요하단 뜻이다.

 

그렇다면, 결국 사이클 한개당 폭탄 한개씩 필요하다고 생각하고, 사이클을 조합으로 골라서 그 사이클에 대한 경우의 수를 구하면 되는 것이었다.

 

박스가 4개일 때 사이클이 한개만 발생하도록 하는것은 생각보다 간단하게 구할 수 있었다.

 

1번박스에선 당연히 열쇠 1번제외 2,3,4 중 열쇠 하나를 매칭.

 

1번박스에서 3번열쇠가 매칭되었을 때 -> 3번박스에서 3번제외 1,2,4번열쇠 중 1번 열쇠를 선택하면 다시 1번박스로 돌아가 사이클이 발생하므로,(사이클 크기2) 반드시 열쇠 2,4중 한개 선택.

 

3번박스에서 2번열쇠가 매칭되었을 때 -> 2번박스에선 남은 열쇠 1,4 중 열쇠1을 선택하면 1번박스로 돌아가 사이클이 발생하므로(사이클 크기3)  4번열쇠 선택.

 

4번박스는 자연스럽게 1번열쇠 매칭

이렇게 사이클이 생기지 않게 하면 결국 크기 4인 사이클 한개만 생긴다.

n=  4 일경우 3 * 2 * 1 ,,, 일반화하면 간단하게 ( n - 1)! 이다.

 

 

그럼 이제 조합을 중복을 고려하여 재귀로 잘 풀면 된다. (크기2인 사이클 4개 -> 8C2 * 6C2 * 4C2 * 2C2 인데 4개이므로 중복되므로 4!을 나눠야 한다).