[알고리즘 스터디] 백준 #1417 국회의원

[문제]

기호 1번으로 출마한 다솜이는 선거 전에 후보별 득표수를 미리 알 수 있다.

다솜이는 득표수를 미리 알아낸 후, 다른 후보를 찍는 사람들을 돈으로 매수해서 자신이 당선되게 하려고 한다.

다솜이가 매수해야 할 사람의 최솟값을 구해라.

 

[Input]

N(후보의 수)

둘째 줄 부터 각 후보의 득표수가 N줄에 걸쳐서 입력된다.

 

[Output]

매수해야 할 사람의 최솟값

 

[풀이]

완전탐색

우선 가장 기본적인 방법으로 접근해보자.

 

전체 후보의 득표수가 votesNum[] 안에 순차적으로 저장되어 있다고 하자.

후보가 3명이고 각 후보의 예상 득표수가 5,7,7이었다고 하자.

voteNum[]에서 max 위치를 구하고, 다솜이(기호 1번)가 최댓값이 아닐 경우 

해당 max 위치에서 1을 빼고, 그 표를 다솜이에게 더해준다.

위 과정을 반복해서 다솜이의 표가 max하다고 나오면, loop를 종료하고 지금까지 돌아간 loop횟수를 print해주면 된다.

 

그렇다면, 완전탐색으로 구현했을 때 제한시간을 만족할 수 있을까?

N(후보자의 수)의 최댓값이 1000이고, 각 후보가 득표할 수 있는 수의 최댓값도 1000이다.

이런 상황에서의 최악의 경우는 위의 사진에서와 같다.

결과적으로 최악의 상황에서도 999번만 loop를 돌리면 output을 구할 수 있기 때문에 완전탐색으로 충분히 구현이 가능하다.

** 한번의 loop에서 최댓값을 구할 때, N만큼의 복잡도가 추가로 소요되어 최악의 반복횟수는 1000*1000이다.

하지만 이 값도 여전히 2초안에 충분히 수행 가능하다.

 

[코드]

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

using namespace std;

int main() {
	int voteNum[1001] = {0,}; //최대 후보자 수 1000명
	int N;
	scanf_s("%d",&N);
	for (int i = 0;i < N;i++) {
		scanf_s("%d", &voteNum[i]);
	}
	int M = 0;
	int maxCount = 0;
	for (int i = 0;i < N;i++) {
		if (voteNum[i] > voteNum[M])
			M = i;
		if (M == 0 && voteNum[i] == voteNum[M])
			M = i;
	}
	for (int i = 0;i < N;i++) {
		if (voteNum[i] == voteNum[M])
			maxCount++;
	}
	int count=0;
	while (M != 0 || maxCount > 1) {
		count++;
		voteNum[M]--;
		voteNum[0]++;
		M = 0;
		maxCount = 0;
		for (int i = 0;i < N;i++) {
			if (voteNum[i] > voteNum[M])
				M = i;
			if (M == 0 && voteNum[i] == voteNum[M])
				M = i;
		}
		for (int i = 0;i < N;i++) {
			if (voteNum[i] == voteNum[M])
				maxCount++;
		}
	}
	printf("%d", count);
}

 

M은 최댓값의 인덱스

maxCount는 최댓값의 수 를 담는 변수이다.

while의 조건을 보면, M이 0(다솜이가 1등)이어도 maxCount가 1 이상이라면 동점자가 있다는 뜻이기 때문에 maxCount에 대한 조건도 추가해주었다. 

 

[제출결과]