[JAVA] 백준 1413번 박스 안의 열쇠

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

1413번: 박스 안의 열쇠

박스안의 열쇠문제... 사이클 수를 구하는 방법을 내가 이해한 걸 적어본다.

폭탄을 터뜨려서 모든 박스를 열 수 있는 확률을 구하는 문제...

 

폭탄을 터뜨려서 열 수 있는 박스는 사이클이 형성된 박스이다.

예를들어 3개의 박스 1, 2, 3 번 박스 안에 열쇠가 아래와 같이 되어있다면,

 

(1)  1 / 2 / 3 -> 사이클 3개(박스를 모두 열려면 폭탄이 3개가 필요)

(2)  1 / 3 / 2 -> 사이클 2개(박스를 모두 열려면 폭탄이 2개가 필요)

(3)  2 / 1 / 3 -> 사이클 2개(폭탄이 2개 이하인 경우 박스를 모두 열 수 있음)

(4)  2 / 3 / 1 -> 사이클 1개(폭탄이 1개만 있어도 박스를 모두 열 수 있음 / 사이클 : 3 -> 1 -> 2 -> 3)

(5)  3 / 1 / 2 -> 사이클 1개(사이클 : 3 -> 2 -> 1 -> 3)

(6)  3 / 2 / 1 -> 사이클 2개

 

3개 박스 사이클을 구하기 위해, 2개 박스인 경우를 살펴보자. (변수 d[박스 수][사이클 수]를 선언했다고 하자)

1 / 2 -> 사이클 2개 : [1 -> 1] / [2 -> 2] (d[2][2] = 1)

2 / 1 -> 사이클 1개 : [2 -> 1 -> 2] (d[2][1] = 1)

 

1 / 2 에서 3번자리에 열쇠 3이 들어간 박스를 추가하면(1 / 2 / 3) 사이클 3개인 박스3개가 된다.

--> 위에서 (1)번 : [1 -> 1] / [2 -> 2] / [3 -> 3]

2 / 1 에서 3번자리에 열쇠 3이 들어간 박스를 추가하면(2 / 1 / 3) 사이클 2개인 박스 3개가 된다.

--> 위에서 (3)번 : [2 -> 1 -> 2] / [3 -> 3]

==> 즉 박스가 2개인 상태에서 구했던 사이클에서 3번째 3번 열쇠가 들어간 박스를 추가하면 기존 사이클에서 1개의 사이클만 추가된다.

d[3][3] 는 d[2][2]를 포함.

d[3][2] 는 d[2][1]를 포함.

 

 

사이클이 하나인 2 / 1 인 상태에서는 [1번째 박스(index) -> 2번째 박스 -> 1번째 박스] 와 같이 움직이는데, 각각의 화살표 (->) 위치에 3을 넣을 수 있다.

- [1 index -> 3 index -> 2 index -> 1 index] ( 3 / 1 / 2 ) -> 위에서 (5) 번.

- [1 index -> 2 index -> 3 index -> 1 index] ( 2 / 3 / 1 ) -> 위에서 (4) 번.

 

사이클이 두개인 1 / 2 인 상태에서는 1 -> 1 / 2 -> 2 로 각각의 사이클이 있다. 여기서 화살표 (->)에 3을 넣을 수 있다.

- [1 -> 3 -> 1] / [2 -> 2] ( 3 / 2 / 1 ) -> 위에서 (6) 번.

- [1 -> 1] / [2 -> 3 -> 2] ( 1 / 3 / 2 ) -> 위에서 (2) 번.

 

이제 규칙이 보일 것이다.

d[i][j] 는 d[i-1][j] 에 화살표가 위치해 있는 자리 수에 각각 i 값을 넣는 경우의 수만큼을 가질 수 있다.

그러므로 d[i][j] 는 d[i-1][j] * (i-1) 을 포함한다.

 

그럼 위에서 d[i][j] 는  d[i-1][j-1] 을 포함하고, d[i-1][j] * (i-1)을 포함하는 규칙을 확인했으니

그 둘을 합쳐보자.

 

d[i][j] = d[i-1][j-1] + d[i-1][j]*(i-1) 

 

라는 것을 확인할 수 있다.