[백준] 1947번: 선물 전달 - python

문제 보기

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

1947번: 선물 전달

 

 

 

 

---

 

풀이 및 코드

 

해당 문제는 복잡한 코드보다는 점화식을 찾는 것에 비중을 둔 문제이다. 

 

 

처음에는 본인에게 선물을 하는 경우들을 찾아 n!에서 빼려고 했다. 하지만 그럴 경우 1명만 본인에게 선물할 경우, 2명만 선물할 경우 ... 로 이어져 결국 n^2의 시간 복잡도를 가진다. n의 범위가 1 <= n <=1000,000 이기에 어림도 없다ㅎ

 

 

따라서 n명일 때의 선물은 n-1이랑 관련이 있다고 생각하고 곰곰이 생각해보았고 다음과 같은 식을 도출할 수 있었다. 

dp[i] = (i-1) * (dp[i-1] + dp[i-2])

 

dp[3]은 3명 즉 1, 2, 3의 사람들끼리 선물 교환을 한 상태이다. 이 상황에서 4번이 추가 됐다고 생각해 보자. 이미 1, 2, 3 끼리 교환을 한 상태에서 4번과 교환한다. 4번은 1, 2, 3 누구랑 바꾸어도 상관이 없다.  만일 1번이 받은 선물을 4번이랑 바꾼다고 한들 1번과 4번은 다른 이들의 선물을 받았기 때문이다. 

 

하지만 빼먹은 것이 있다. 1, 2, 3 끼리 교환을 한 상태라면, 1번은 다른 이의 선물을 들고 있다. 하지만 1번과 4번이 교환을 할 것이라면 1번이 굳이 다른 이들의 선물을 들고 않아도 된다. 따라서 1번과 4번이 교환하고 나머지 인원들끼리 교환하면 된다! 

 

따라서 두 경우를 합해 점화식을 세운다면 dp[i] = (i-1) * dp[i-1] +  (i-1) * dp[i-2] 이 된다.

 

 

 

이해를 위해 상황을 가정해서 설명했는데 도움이 되었으면 좋겠다ㅎ 만일 더 어렵다면, 직접 써가며 이해하는 것을 추천한다!