05_볼링공 고르기

주어진 볼링공의 개수(N)이 1,000 이하고, 시간 제한은 1초였다.

그러므로 O(N^2)의 시간복잡도로 충분히 풀 수 있다.

 

그래서 처음에는 단순하게 1번~N번의 볼링공까지 for문을 돌면서 자기 다음 번호 ~ N번까지의 공들을 확인해서 자기 자신과 같은 값 빼고 +1을 해주면 답이 나온다고 생각했다.

 

좀 더 생각해보니 더 간단한 로직이 있었다.

각 볼링공 무게를 인덱스로 하는 리스트를 만들어서 볼링공 무게마다 볼링공이 몇개 있는지 저장한다.

그 후 특정 볼링공 무게에 해당하는 볼링공의 개수가 0이 아닌 경우,

특정 볼링공 무게의 볼링공 개수 개수 * (전체 볼링공 개수 - 특정 볼링공 무게의 볼링공 개수)

를 무게마다 구해서 더해준 다음에 2로 나눠주면 답이 나온다.

 

내 풀이

# Q_05_볼링공 고르기
n, m = map(int, input().split()) # 볼링공의 개수 n, 공의 최대 무게 m
arr = list(map(int, input().split())) # 볼링공들을 입력받기 위한 임시 리스트 arr
balls = [0] * (n+1) # 각 인덱스(볼링공 무게)에 해당하는 볼링공 개수를 나타내는 리스트 balls

# balls 리스트의 인덱스에 해당하는 볼링공의 개수 추가
for ball in arr:
    balls[ball] += 1

# 볼링공 번호의 조합의 총합
total = 0


for ball in balls:
    if ball != 0: # 해당 볼링공 무게에 해당하는 볼링공 개수가 0이 아닌 경우
        total += (n - ball) * ball # 해당 볼링공 무게에 해당하는 조합 수

print(total//2) # 2로 나눠줘야 중복이 제거된다.

 

 

답지에서는 거의 비슷하게 했으나, 

A가 특정한 무게의 볼링공을 선택한 후, B가 볼링공을 선택하는 경우를 차례대로 계산해서 문제를 해결했다.

 

예를 들어, 볼링공의 개수가 5, 무게는 3 이하이고 공이 1, 3, 2, 3, 2로 주어졌다면

1. A가 무게가 1인 공을 선택한 경우 -> 1(무게가 1인 공의 개수) * 4(B가 선택하는 경우의 수) = 4가지 -> 1C1 * 4C1

2. A가 무게가 2인 공을 선택한 경우 -> 2(무게가 2인 공의 개수) * 2(B가 선택하는 경우의 수) = 4가지 -> 2C1 * 2C1

3. A가 무게가 3인 공을 선택한 경우 -> 2(무게가 3인 공의 개수) * 0(B가 선택하는 경우의 수) = 0가지 -> 2C1 * 0C0

로 총 8개가 나온다.

 

여기서 단계가 진행됨에 따라 B가 선택하는 경우의 수는 줄어드는데, 이미 계산했던 경우(조합)는 제외하기 때문이다.

조합 계산하는 법!

 

풀이 코드

# Q_05_볼링공 고르기
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)