문제

A,B 두 사람이 서로 무게가 다른 공으 고르려 한다. 볼링공은 총 N개가 있으며, 각 볼링공 마다 무게가 적혀있고, 공의 번호는 1번부터 순서대로 부여. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주. 볼링공의 무게는 1부터 M까지의 자연수로 존재.

예를 들어 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)

입력 조건

• 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어짐. (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10)
• 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어짐 (1 ≤ K ≤ M)

출력 조건

• 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력

풀이 (맞)

N, M = map(int, input().split())
ball_list = list(map(int, input().split()))
ball_count = [0] * 11
for ball in ball_list:
  ball_count[ball] += 1
result = 0
for i in range(1,11):
  for _ in range(ball_count[i]):
    for j in range(i+1,11):
      result += ball_count[j]

print(result)

사고의 흐름

우선 중요한것은, ‘무게가 다른’ 공을 골라야 하는 것이며, 같은 무게라도 다른 공으로 취급한다는 것이었다.

정렬을 해야할까를 생각하면서, 공의 순서나 번호가 중요한것은 아니고, 다른 공이라는 사실만 중요한것 같았다. 그래서 정렬을 하고 내가 다시 번호를 매기기로 했다.

그리고 문제 예제에서 순열이 아니고 조합을 구하니 (낮, 높) 순서대로 가기로 하였고, 최대 무게인 M이 10 이하기 때문에, 각 무게별로의 카운트 리스트를 해도 공간상이나 시간상 문제가 없을것 같았다. (세그트리 같은 이상한거 안써도 되네…)

예제에서 8가지 경우의 수는

• 무게가 1인 공 1번을 낮으로 했을 때 : 그거보다 높은건 4개
• 무게가 2인 공 2번을 낮으로 했을 때 : 그거보다 높은건 2개
• 무게가 2인 공 3번을 낮으로 했을 때 : 그거보다 높은건 2개
• 무게가 3인 공 4번을 낮으로 했을 때 : 그거보다 높은건 없음