[백준/C & C++] 1417 국회의원 선거

https://www.acmicpc.net/problem/1417

1417번: 국회의원 선거

C

#include <stdio.h>

int arr[51];

typedef struct maxValue {
	int index;
	int value;
} result;
result fin;

void find(int n)
{
	fin.value = arr[0];
	fin.index = 0;
	
	for (int i = 1; i < n; i++)
	{
		if (fin.value < arr[i])
		{
			fin.value = arr[i];
			fin.index = i;
		}
	}
}

int main()
{
	int n, dasom, result=0;
	scanf("%d", &n);
	scanf("%d", &dasom);
	for (int i = 0; i < n - 1; i++) scanf("%d", &arr[i]);

	if (n == 1)
	{
		printf("%d", result);
		return 0;
	}
	find(n - 1);
	while (dasom <= fin.value)
	{
		dasom++;
		arr[fin.index]--;
		result++;
		find(n - 1);
	}
	printf("%d", result);
	return 0;
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n, dasom, num, result = 0;
	vector <int> d;
	cin >> n;
	cin >> dasom;
	for (int i = 0; i < n - 1; i++)
	{
		cin >> num;
		if (num >= dasom) d.push_back(num);
	}
	if (d.size())
	{
		while (dasom <= *max_element(d.begin(), d.end()))
		{
			dasom += 1;
			int index = max_element(d.begin(), d.end()) - d.begin();
			d[index]--;
			result++;
		}
	}
	cout << result;
	return 0;
}

코드 설명

📌 다솜이의 표가 가장 많아질 때까지 표를 가장 많이 받은 사람의 표를 다솜이한테 옮기면 된다.

C

find함수 : 최댓값과 최댓값의 인덱스를 구한다. 

 최댓값과 최댓값의 인덱스를 저장하는 구조체를 하나 만들었다. 굳이 안 만들어도 되는데 하나로 묶어두고 싶어서 나는 구조체에 값들을 저장했다. 인덱스 0과 인덱스 0에 저장된 값으로 초기화하고, 반복문을 돌면서 실제 최댓값과 최댓값의 인덱스를 구한다.

 

main함수

국회의원 후보 수 n과 다솜이의 득표 수 dasom을 각각 입력받는다. 이후 반복문을 이용해서 국회의원 후보들이 받은 득표 수를 입력받아 배열에 저장한다. n==1이라면 다솜이 혼자 출마한 것이므로 0을 출력하고 프로그램을 종료한다. 

그렇지 않은 경우에는 반복문을 이용해서 매수해야 할 사람 수를 구해준다. 이때 먼저 find(n-1)을 실행해서 처음 상태의 최댓값과 최댓값의 인덱스를 구한 뒤에 반복문을 실행한다. 다솜이의 득표수와 매수할 사람 수를 1씩 증가시키고, 현재 표를 가장 많이 받은 사람의 득표수를 1 감소시킨다. 반복문의 마지막에  find(n-1)을 작성해서 최댓값과 최댓값의 인덱스를 갱신한다. (find함수를 반복문 안, 밖에서 호출한 걸 고쳐보고 싶어서 do-while문으로도 썼었는데, 그럴 경우에는 반복문 내에 if문을 써서 다솜이가 최다 득표자인지 확인하는 작업을 해야 한다. 고민하다가 그냥 while문으로 작성했다.) while문이 끝나고 result를 출력하고 프로그램을 종료한다. 

 

C++

국회의원 후보 수 n과 다솜이의 득표 수 dasom을 각각 입력받는다. 이후 반복문을 이용해서 국회의원 후보들이 받은 득표 수를 입력받아 vector에 저장한다. 이때 이미 표 수가 다솜이보다 적은 후보는 신경 쓸 필요가 없으니 vector에 저장하지 않는다.  vector에 저장된 수가 1개이상이라면 반복문을 실행하고 그렇지 않을 경우에는 바로 0을 출력하고 프로그램을 종료한다. 반복문 내에서는 최댓값과 최댓값의 인덱스를 이용해서 result에 값을 더해나간다. *max_element(d.begin(), d.end())는 vector에서의 최댓값이고, max_element(d.begin(), d.end()) - d.begin()는 최댓값이 저장된 인덱스이다. 값을계속 변경하다가 다른 후보 득표수 중 최댓값이 다솜이의 득표수보다 작아지면 반복문을 종료하고 결과를출력하면 된다.

 

느낀 점

C++의 경우에는 학회에서 STL을 배워서 적용하는 연습 중이다. 처음에는 약간 어색했는데 코드가 간결해지는 게 눈으로 보여서 열심히 쓰려고 하고 있다. 이 문제는 10달 전에 시도했다가 실패한 문제였는데, 갑자기 아이디어가 떠올라서 코드를 빠르게 작성했다!