볼링공 고르기 - 그리디

  A가 어떤 공을 고르면, B는 반드시 A가 고른 공과는 다른 무게를 가진 공을 골라야 한다. 그리고 이 문제에서 중요한 것은 두 사람중 어떤 사람이 공을 집었는지는 사실 상관 없다는 것이다. 다시말해 A가 1번 공을 집고 B가 2번  공을 집는 경우와 A가 2번 공을 집고 B가 1번 공을 집는 경우는 완전히 같은 경우라는 말이다. 따라서 단순히 조합문제로 다음과 같이 풀 수 있다.

from itertools import combinations
from collections import Counter

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

result = 0
for c in combinations(Counter(data).items(),2):
  temp = list(map(lambda x : x[1],c))
  result += temp[0]*temp[1]

print(result)

 하지만 그리디처럼 풀 수도 있는데, 접근법 자체는 동일하나 반복문을 돌며 중복된 선택은 제외 한다.

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

cnt = [0]*11
for w in data:
  cnt[w] += 1

result = 0
for w in range(1,m+1):
  n -= cnt[w]
  result += cnt[w]*n

print(result)