11-5. 볼링공 고르기

1. 문제

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번)

결과적으로 두 사람이 고르는 경우의 수는 8가지 입니다. N개의 공의 무게가 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.

2. 입력

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

3. 출력

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

4. 풀이1

• 처음에는 그냥 차례대로 탐색하면서 다른 거 개수 세면 되지 않나 싶었다.
• 근데 그러면 O(N^2)이 나오고 최대 무게도 필요가 없었다.
• 더 효율적인 알고리즘이 있을텐데 생각이 안나서 우선 코드를 써봤다.

5. 코드

#include <iostream>

using namespace std;

int arr[1000];

int main(){
	int n, m, cnt=0;
	scanf("%d %d", &n, &m);
	
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	for(int i=0; i<n-1; i++){
		for(int j=i+1; j<n; j++){
			if(arr[i]!=arr[j]) cnt++;
		}
	}
	
	cout<<cnt<<endl;
}

6. 풀이2

• 더 효율적인 알고리즘을 봤는데 컨셉은 이해가 되는데 구체적인 풀이가 이해가 안 가서 직접 써봤다.
• (전체 무게의 수) - (현재 무게의 수)가 가장 기본적인 경우의 수다.
• 근데 같은 무게는 다르게 취급하니까 곱해준다.
• {(전체 무게의 수) - (현재 무게의 수)} * (현재 무게의 수)
• 전체 무게의 수는 계속 줄어들어야 해서 미리 빼준다.
• 이러고 나니까 해답이랑 똑같이 나왔다.

7. 코드

#include <iostream>

using namespace std;

int arr[11];

int main(){
	int n, m, cnt=0;
	cin>>n>>m;
	
	for(int i=0; i<n; i++){
		int k;
		cin>>k;
		arr[k]++;
	}
	
	for(int i=0; i<m; i++){
		n-=arr[i];
		cnt += n * arr[i];
	}
	
	cout<<cnt<<endl;
}