[PART3] 5. 볼링공 고르기

코뉴·2021년 1월 3일

그리디 이코테

이코테: 문제풀이

목록 보기

6/28

알고리즘 유형별 기출문제: 그리디

💻 2. 볼링공 고르기

난이도🖤🤍🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB | 2019 SW 마에스트로 입학 테스트

📌2021/01/03 작성 코드

import math

# 입력
n, m = map(int, input().split())
data = [0 for i in range(m)] # 크기가 m인 리스트 data 선언, 0으로 초기화
temp = list(map(int, input().split())) # 입력 받기
for x in temp:
    data[x-1] += 1

# 조합
ret = math.factorial(n)/(math.factorial(n-2) * math.factorial(2))
for i in range(m):
    # 무게가 겹치지 않게 해야 하므로 같은 무게 안에서 2개 선택하는 것을 빼준다
    if data[i] >= 2:
        ret -= math.factorial(data[i])/(math.factorial(data[i]-2) * math.factorial(2))

# 출력
print(int(ret))

나의 경우, 조합 문제를 푸는 아이디어로 풀어냈다.

🤓 문제 해설

이 문제를 효과적으로 해결하기 위해서는, 먼저 무게마다 볼링공이 몇 개 있는지를 계산해야 한다. 문제에서 등장한 예시를 기준으로 보면 다음과 같다.

무게가 1인 볼링공: 1개
무게가 2인 볼링공: 2개
무게가 3인 볼링공: 2개

이때 A가 특정한 무게의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산하여 문제를 해결할 수 있다. A를 기준으로 무게가 낮은 볼링공부터 무게가 높은 볼링공까지 순서대로 하나씩 확인을 한다고 했을 때 다음과 같다.

A가 무게가 1인 공을 선택할 때의 경우의 수는
1(무게가 1인 공의 개수) * 4(B가 선택하는 경우의 수) = 4가지
A가 무게가 2인 공을 선택할 때의 경우의 수는
2(무게가 2인 공의 개수) * 2(B가 선택하는 경우의 수) = 4가지
A가 무게가 3인 공을 선택할 때의 경우의 수는
2(무게가 3인 공의 개수) * 0(B가 선택하는 경우의 수) = 0가지

따라서 가능한 경우의 수는 총 8가지이다.

단계가 진행됨에 따라 'B가 선택하는 경우의 수'는 줄어드는데, 이미 계산했던 경우(조합) 은 제외하기 때문이다. 또한 볼링공의 무게가 1부터 10까지만 존재할 수 있다고 명시되어 있다. 따라서 하나의 리스트 변수를 선언해서, 각 무게별로 볼링공이 몇 개가 존재하는지 기록할 수 있다. 이를 소스코드로 옮기면 다음과 같다.

🤓 답안 예시

n, m = map(int, input().split())
data = list(map(int, input().split()))

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱해주기

print(result)