책 315p

문제

• 입력
  • 첫째줄에 볼링공의 갯수 N, 공의 최대 무게 M이 공백으로 구분되어 자연수로 주어짐
    • (1<=N<=1,000. 1<=M<=10)
  • 둘째줄에 각 볼링공의 무개 K가 공백으로 구분되어 순서대로 자연수 형태로 주어짐
    • (1<=K<=M)
• 출력조건
  • 첫째줄에 두 사람이 볼링공을 고르는 경우의 수 출력

A, B 두사람이 볼링 침.
두 사람은 서로 무게가 다른 볼링공을 고르려고 함.
N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.

예시)
N= 5, M = 3 , 공이 차례로 [1,3,2,3,2] 의 무게 가짐
두 사람이 고를 수 있는 볼링공번호의 조합은 (인덱스 기준) (1,2), (1,3), (1,4), (1,5), (2,3), (2,5), (3,4), (4,5)

풀이

처음 든 생각

나 확통 처돌인가... $nPr$ 로 모든 경우 구하돼, 서로 같은 무게일 경우에는 cotinue 하면 안되나 ?

풀이 아이디어

무게마다 볼링공이 몇 개 있는지 계산한 후,
A가 특정 무게의 볼링공을 선택했을때, B가 볼링공을 선택하는 경우 차례로 계산

예시)
N= 5, M = 3 , 공이 차례로 [1,3,2,3,2] 의 무게 가짐

• 무게가 1인 볼링공 : 1개

• 무게가 2인 볼링공 : 2개

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

• A가 무게 1인 공 선택할때 경우의 수

  • 1 (무게 1인 공 갯수) * 4 (B가 선택하는 경우의 수)

• A가 무게 2인 공 선택할때 경우의 수

  • 2 (무게 2인 공 갯수) * 2 (B가 선택하는 경우의 수)

• A가 무게 3인 공 선택할때 경우의 수

  • 2 (무게 3인 공 갯수) * 0 (B가 선택하는 경우의 수)

풀이 보고 느낀 점

이것도 '결과' 의 모호한 형태 (조합..? 헤헤 .. )보다
'결과의 정확한 출력형태' (조합할 수 있는 '갯수') 에 초점을 맞춰야 정확히 생각할 수 있구나. 갯수만 생각하니까, 그냥 간단히 카운트 하고 끝난다.

코드

n = int(input())
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)