[백준 17358번] [Python] 복불복으로 지구 멸망

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

17358번: 복불복으로 지구 멸망

 

난이도 : 실버5
태그 : 수학, 조합론

 

 

설명

컵 하나와 다른 컵 하나를 서로 바꿉니다.

컵의 갯수는 항상 짝수이며,

모든 컵은 단 한 번만 바뀌어야 할 때,

가능한 조합의 경우의 수를 구하는 문제입니다.

 

 

예시와 함께 보겠습니다.

---

 

6개의 컵이 있다 가정을 해보겠습니다.

 

6개의 컵중 하나를 선택합니다.

 

위치를 옮길 다른 컵 하나를 선택합니다.

5개의 컵 중 하나를 선택할 수 있으므로, 현재까지 경우의 수는 5입니다.

 

다른 컵을 하나 선택합니다. 저는 2번컵을 집었습니다.

 

남은 3개의 컵중 위치를 뒤바꿀 컵 하나를 선택합니다.

3개의 컵 중 하나를 선택할 수 있습니다.

 

현재까지 경우의 수는 5 x 3 = 15입니다.

 

 

 

남은 컵의 개수는 2개밖에 없으므로, 경우의 수는 하나입니다.

즉, 컵의 개수 n = 6 일때, 가능한 경우의 수는 5 x 3 x 1 = 15 입니다.

 

 

 

컵 하나를 선택하고, 다른 컵 하나를 선택한다 생각하니,

컵의 개수가 n이라 했을때, 경우의 수는

(n-1) * (n-1-2) * (n-1-3) * (n-1-5) * ... * (1) 입니다.

 

점화식으로 나타내면, a(n) = a(n - 2) * (n-1)  (단, a >= 4, a(2) = 1, a는 짝수) 로 나타낼 수 있겠네요.

점화식 배운지가 좀 되서 기억이 가물가물한지라... 맞는진 잘 모르겠네요 ㅎㅎ;

 

 

소스코드

n = int(input()) - 1

case = 1
for i in range(n, 1, -2):
    case = case * i

print(case % (1000000000 + 7))

경우의 수를 어떻게 구해야 할지, 어떻게 접근해야 할지가 어렵지

소스코드 자체는 굉장히 간단합니다.

 

 

 

 

후기

오랜만에 작성해보는 파이썬 포스팅입니다.

최근 파이썬을 다뤄볼 일이 생겨 오랜만에 하고 있는데,

와... 굉장히 간단하게 코딩할 수 있네요...

역시 실행 가능한 의사코드란 별명이 괜히 있는게 아닌 것 같습니다.