이코테 볼링공고르기 파이썬

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

ball_count_per_weight = [0] * 11
for ball in balls:
    ball_count_per_weight[ball]+=1

result = 0
for i in range(1, len(ball_count_per_weight)):
    N-= ball_count_per_weight[i]
    result+=ball_count_per_weight[i] * N

print(result)    
# 8 5
# 1 5 4 3 2 4 5 2

 

이 문제의 조건은

1. A와 B 두명이 서로 다른 무게의 볼링공을 골라야하며,

2. 같은 무게의 공이 여러개 있더라도 다른 공이므로 다시 고를수 있다.

 

곧이 곧대로 푼다면 2중 for loop 로 간단히 풀 수 있다. 

하지만 이 문제는 위 소스처럼 O(N)으로 풀 수 있다.

볼링공의 무게별 카운트를 저장한다음,

A가 특정 무게의 공을 골랐다면

해당 무게의 공의 갯수 * 해당 무게의 공을 제외한 나머지 공의 갯수를 누적하면 정답을 찾을 수 있다.

 

이것도.. 알고리즘에 익숙치 않다면 일반적으로 생각하기 쉽지 않은듯하다.