[C/C++] 나동빈 볼링공 고르기, Greedy

문제

A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개이며 각 볼링공마다 무게가 적혀있고 공의 번호는 1번부터 순서대로 부여된다. 같은 무게의 공이 두 개 있을 수 있지만 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. 이때 두 사람이 서로 다른 볼링공을 고르는 경우의 수를 구하라. 예를 들어 볼링공이 5개이고 각 볼링공이 번호 순서대로 1, 3, 2, 3, 2라면, 경우의 수는 8이다.

코드

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
	int N, M, num, result = 0;
	int B[11] = { 0 };
	scanf_s("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		cin >> num;
		B[num] += 1;
	}


	for (int i = 1; i < M + 1; i++) {
		N -= B[i];
		result += B[i] * N;
	}
	cout << result;
}

풀이