[그리디] 볼링공 고르기

A, B 두 사람이 볼링을 치고 있다. 볼링공은 총 N개 있고 볼링공의 무게는 각각 다르며 1부터 M까지의 자연수 형태로 무게가 존재한다.(1 <= N <= 1000, 1 <= M <= 10) 같은 무게의 공이 여러개 있을 수 있고 서로 다른 공으로 간주한다. 예를 들어 N이 5이고 M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2 일 때 각 공의 번호가 차례대로 1번부터 5번 까지 부여된다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같다.

 

(1번공, 2번공), (1번공, 3번공), (1번공, 4번공), (1번공, 5번공), (2번공, 3번공), (2번공, 5번공), (3번공, 4번공), (4번공, 5번공)

 

결과적으로 두 사람이 공을 고르는 경우의 수는 8가지다. 

 

위의 예에서 (1번공, 2번공) 이 선택 되었을 때, (2번공, 1번공) 은 선택되지 않는다. 같다고 보는것이다.

제일 먼저 생각난것은 이중 for문이었다. i 번째 인덱스의 값과 i+1부터 끝까지의 값을 전부 비교하면서 같지 않으면 count를 늘려가는 방식이다. 이중 for문이니 시간복잡도가 O(n^2) 로 안좋지만 볼링공 최대 갯수가 1000 개 이므로 괜찮다고 판단했다.

N, M = map(int, input().split())
data = list(map(int, input().split()))

count = 0
for i in range(0, int(N)):
	for j in range(i+1, int(N)):
		if data[i] != data[j]:
			count += 1

print(count)

 

하지만 이 방법은 N이 엄청 클 때는 적합한 알고리즘이 아니다. 아까 1, 3, 2, 3, 2 를 갖고 다른방법으로 풀어보자.  먼저 무게 마다 볼링공 갯수를 구한다.

w1 인 볼링공 : 1개

w2 인 볼링공 : 2개

w3 인 볼링공 : 2개

 

step1 : A가 w1 인 공을 선택할 때의 경우의 수는 1(w1인 공의 갯수) * 4(B가 선택하는 경우의 수) = 4 가지

step2 : A가 w2인 공을 선택할 때의 경우의 수는 2(w2인 공의 갯수) * 2(B가 선택하는 경우의 수) = 4 가지

step3 : A가 w3인 공을 선택할 때의 경우의 수는 2(w3인 공의 갯수) * 0(B가 선택하는 경우의 수) = 0 가지

 

따라서 총 8가지다.

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):
	# 무게가 i 인 볼링공의 갯수(A가 선택할 수 있는 갯수) 제외
	# 즉 array[i] 만큼 빼진 n은 B가 선택하는 경우의 수다.
	n -= array[i]
	# 무게가 i 인 공의 갯수와 B가 선택하는 경우의 수 곱하기
	result += array[i] * n

print(result)

 

출처 : 이것이 코딩테스트다 나동빈 저