[이코테] 그리디 알고리즘 - 볼링공 고르기

N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.
(같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주 )

 

📌 입력 조건

1. 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다. 
   (1 <= N <= 1,000, 1 <= M <= 10)
2. 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다

📌 출력 조건

1. 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.

 

📌 입력 예시

5 3
1 3 2 3 2

8 5
1 5 4 3 2 4 5 2

📌 출력 예시

8

25

---

📌 풀이

• 위의 입력 예시에서 A가 무게 1의 공을 선택했을 때 B가 선택할 수 있는 경우의 수는 4가지다.
• A가 무게 2의 공을 선택했을 때 계산했던 무게 1의 공을 제외하고 B가 선택할 수 있는 경우의 수는 4가지다.
• A가 무게 3의 공을 선택했을 때 계산했던 무게 1과 2의 공을 제외한 B가 선택할 수 있는 경우의 수는 0가지다.
• B가 선택할 수 있는 경우의 수가 줄어드는데 이미 계산했던 경우는 제외되기 때문이다.

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

array = [0] * 10

for x in data:
    array[x - 1] += 1

result = 0
for i in range(m):
    n -= array[i]
    result += array[i] * n

 

머리가 안좋은건가..? 문제를 푸는건지 문제를 그냥 쳐다보고 있는건지..ㅎㅎ
처음에 접근방법이 아예 잘못됐다. 익숙하지 않아서 그렇다고 이번에도 자기 위안삼는다 주륵..
무족건 복습하자