[JAVA] 백준 1947번 선물 전달

→https://www.acmicpc.net/problem/1947

1947번: 선물 전달

위 문제는 백준 1413번 박스 안의 열쇠와 매우 유사한 문제인것 같아 오랜만에 글 올려본다.

https://djjblog.tistory.com/26

( ↑ 백준 1413번 박스 안의 열쇠)

 

선물을 돌리는데 자신의 것은 받을 수 없다면 결국은 사이클이 있어야 한다는 점.

그 점을 이용해서 다이나믹 프로그래밍 알고리즘으로 푸는 문제이다.

n (사람의 수)이 1인 경우는 내가 내자신의 선물을 받는 경우밖에 없으므로 0이 된다.

n 이 2 인 경우에는 상대방의 선물을 받는 경우밖에 없으므로 경우의 수는 1이 된다.

 

n이 3이상부터는 이전에 계산한 경우의 수를 이용하면 된다.

n이 4인 경우를 봐보자.

 

기존에 3명까지 선물을 주고 받는 경우의 수를 구했다고 가정하면,

(1) 1 / 2 / 3 / 4 

→  기존 3명에서 4번째에 한명이 더 추가된 것이다. 

4번째 추가된 사람이 내 선물을 내가 받으면 안되니, 기존에 있던 사람중 한명과 서로 주고 받는다고 하면,

(3명중 한명을 선택한 수 * 4명중에 4번째 자신과 선물을 주고받을 한명을 제외한 수가 선물을 주고받는 경우의 수)

→ 3 * d[2] → (n-1) * d[n-2]

 

(2) 1 / 2 / 3 / 4 

→ 4번째 사람이 추가되어 다른사람 선물을 받았는데, 그 다른사람과 서로 주고받는 경우가 아닌 경우.

간단히 말하면 기존에 3명(n-1)명이 이미 사이클이 형성되어 있는데 거기에 4번째 사람이 들어가는 경우이다.

d[n-1] 에서 사이클은 3개가 형성되어 있을 테니 n-1만큼 곱해주면 된다.

→ 3 * d[3] → (n-1)*d[n-1]

 

한명이 추가될 때마다 위와 같은 경우의 수가 추가 된다고 가정하면

d[n] = (n-1) * d[n-1] + (n-1) * d[n-2] = (n-1) * (d[n-1] + d[n-2])

위와 같이 표현 할 수 있다.