[그리디 알고리즘] 볼링공 고르기 ★☆☆

문제 : A, B 두 사람은 서로 다른 무게의 볼링공을 선택하려고 한다. 그 경우의 수를 구하라

 

입력 조건

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

출력 조건

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

입력 예시 1

5 3
1 3 2 3 2

출력 예시 1

8

입력 예시 2

8 5
1 5 4 3 2 4 5 2

출력 예시 2

25

---

동전을 하나씩 추가하면서 경우의 수를 계산해 주면 된다

 

이 문제가 왜 그리디 문제인지 모르겠다

---

#include<bits/stdc++.h>
using namespace std;
int n, m;
int ball[11];
int tmp;
int ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0;i < n;i++) {
        cin >> tmp;
        ball[tmp]++;
    }
    for (int i = 2;i <= m;i++) {
        for (int j = 1;j < i;j++) {
            ans += ball[i] * ball[j];
        }
    }
    cout << ans;
    return 0;
}