볼링공 고르기

출처:: 2019 sw마에스트로 입학 테스트

분류:: 그리디 

 

1. 문제 이해 및 해결과정

1번 풀이 1) n개 중에 2명이 뽑는 경우의 수  2) 같은 무게를 뽑는 경우   => 1번 - 2번  2번 풀이 1) 각 무게 마다 볼링공 몇 개 있는지   2) 경우의 수 더하기   ex) 1 2 2 3 3 이라면 [1,2,2,]     1. A가 무게가 1인 공을 선택할 때 경우의 수 -> 1*4(B가 선택할 수 있는 경우의 수 5-1) = 4     2. A가 무게가 2인 공을 선택할 때 경우의 수 -> 2*2(B가 선택할 수 있는 경우의 수 4-2) = 4     3. A가 무게가 3인 공을 선택할 때 경우의 수 -> 2*0(B가 선택할 수 있는 경우의 수 2-2) = 0     => 8가지

 

 

2. 풀이방법

  1. 조합

#볼링공 고르기
#
'''
5 3
1 3 2 3 2
#8
8 5
1 5 4 3 2 4 5 2
#25
'''
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
li=list(map(int,input().split()))
w=[0]*(m+1)

for x in li:
    w[x]+=1

sum=0
for x in w:
    sum+=int(x*(x-1)//2)

com=n*(n-1)//2
print(com-sum)

 

  2. 그리디

#볼링공 고르기
#
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
li=list(map(int,input().split()))

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

for x in li:
    arr[x]+=1

res=0
for i in range(1,m+1): #각 무게에 대해서
    n-=arr[i] #A가 선택할 수 있는 개수
    res+=arr[i]*n #A가 선택할 수 있는 개수 * B선택하는 경우

print(res)

 

3. 오답원인

 

4. 알게된 점