[파이썬 풀이] 25345번: 루나의 게임 세팅 - 백준

백준 25345번: 루나의 게임 세팅

알고리즘 분류: 수학. 조합론

파이썬(Python) 풀이

 

링크: https://www.acmicpc.net/problem/25345

문제

루나와 리나는 타워 건설 게임을 하려고 한다. 타워 건설 게임은 K개의 타워를 사용하는 게임이고 루나는 이 게임을 세팅하려고 한다.

게임 세팅은 서로 다른 높이의 N개의 타워 중 K개를 선택해 원하는 순서로 일렬로 배치하는 것이다. 이때 앞과 뒤에서 바라볼 때 모든 타워가 최소 한 번은 보여야 한다. 즉, 어떤 타워에 대해서 그보다 높은 타워가 그 타워의 앞쪽과 뒤쪽에 모두 존재하면 안된다는 것이다. 

게임 세팅을 하던 루나는 문득 게임을 세팅하는 방법이 얼마나 많을 지가 궁금해졌다. 루나를 도와서 게임 세팅을 하는 경우의 수를 구해보자. 

---

입력

첫째 줄에는 두 양의 정수 N과 K가 주어진다.

둘째 줄에는 각각의 타워의 높이 A₁,A₂,⋯,An이 공백으로 구분되어 주어진다.

모든 입력은 정수이다.

---

출력

게임 세팅을 할 수 있는 경우의 수를 10⁹+7로 나눈 나머지를 출력한다. 

---

풀이

이 문제의 예제는 한개가 주어진다.

입력과 출력은 다음과 같다.

# 입력
5 3
1 6 7 9 11

# 출력
40

타워의 개수는 5개, 그리고 3개의 타워를 이용했을 때의 경우의 수를 구하는 것이다.

 

이 문제에 대하여, 예제를 통해 설명하자면

먼저 타워 5개중 사용할 3개를 뽑아야 하는 경우의 수 : 5C3 = 10가지

그렇게 뽑힌 타워가, 높이가 6, 9, 11일 때,

 

[6, 9, 11]

[6, 11, 9]

[9, 11, 6]

[11, 9, 6] 이렇게 4가지이다.

따라서 10 * 4 = 40가지가 나온다.

---

 

그러면 어떻게 이런 생각을 떠올릴 수 있는것인가? 라고 한다면,

답은 크기가 가장 큰거부터 세우면 된다.

먼저 높이가 11인 타워를 세운다.

 

 

그리고 그 타워를 기준으로 높이가 9인 타워를 어느쪽에 세울 지 정한다. 

 

그렇게 높이가 9인 타워를 세웠다면, 그 다음의 높이가 6인 타워를 양쪽중 어느쪽에 세울지 정한다.

 

그렇게 되면 다음과 같은 결과가 나타난다.

 

이걸 단순화 한다면 K개중에 높이가 가장 큰걸 제외한 K-1개가 각각 왼쪽, 오른쪽인 2개의 방향중 한 방향을 고르는 것이므로

2ⅡK-1 = 2^(K-1)라고 볼 수 있다.

 

따라서 NCK * 2^(K-1)라고 정리할 수 있다.

---

 

코드로 구현하면 다음과 같다.

factorial을 math모듈에서 선언한 뒤, N과 K를 입력받고, 배열 arr을 (솔직히 의미없긴하지만) 입력 받고,Combination 식을 기반으로 그대로 쓰면 된다. 또한 마지막에 10의 9제곱 + 7의 나머지로 구하는 것도 잊지 말아야 한다.