[ 그리디 ] 05 볼링공 고르기

난이도 : 하 풀이시간 : 30분 시간제한 : 1초 기출 : 2019 SW 마에스트로 입학 테스트

[ 그리디 ] 05 볼링공 고르기

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개의 공의 무게가 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.

 

:: 입력 조건

 

첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.

(1<=N<=1,000, 1<=M<=10)

둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.

 

:: 출력 조건

 

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

 

---

 

  내   코드  

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

using namespace std;

int main()
{
	int n = 0, m = 0, cnt = 0;
	cin >> n >> m;

	vector<int> ws;

	for (int i = 0; i < n; i++) {
		int k = 0;
		cin >> k;
		ws.push_back(k);
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (ws[i] != ws[j]) {
				cnt++;
			}
		}
	}

	cout << cnt;
}

제일 먼저 생각난 풀이는 이건데

시간복잡도가 구리고 이럴거면 최대 무게 제한 둘 필요도 없고 ,,

문제가 원하는 답은 아닌 거 같아서 답지 봄

 

  정답  코드  

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

using namespace std;

int main()
{
	int n = 0, m = 0, cnt = 0;
	int w[11] = { 0, };

	cin >> n >> m;

	vector<int> ws;

	for (int i = 0; i < n; i++) {
		int k = 0;
		cin >> k;
		w[k]++;
	}

	for (int i = 1; i <= m; i++) {
		n -= w[i];
		cnt += n * w[i];
	}

	cout << cnt;
	return 0;
}

 

  리뷰  

무게의 범위가 1에서 10까지니까

해당 무게의 공이 몇 개 있는지 담아둘 배열을 만듦

 

예시 입력 [ 5 3 / 1 2 3 2 3 ] 기준

 

A가 무게 1인 공을 골랐을 때 ( 1 ) -> B가 고를 수 있는 경우 ( 4 - 2, 3, 2, 3 ) 

A가 무게 2인 공을 골랐을 때 ( 2 ) -> B가 고를 수 있는 경우 ( 2 - 3, 3 )

A가 무게 3인 공을 골랐을 때 ( 2 ) -> B가 고를 수 있는 경우 ( 0 )