백준 문제풀이

1417번 : 국회의원 선거

하다블 2022. 4. 5. 18:47
반응형

문제는 다음과 같습니다.

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

 

1417번: 국회의원 선거

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같

www.acmicpc.net

풀이 코드는 다음과 같습니다.

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

int main()
{
	int count{0};
	int temp;
	int dasom;
	vector<int>v;
	cin>>temp;
	cin>>dasom;
	for(int i{0};i<temp-1;i++)
	{
		int num;
		cin>>num;
		v.push_back(num);
	}
	while(true)
	{
		int maxi{0};
		int idx{0};
		for(int i{0};i<temp-1;i++)
		{
			if(maxi<v[i])
			{
				maxi=v[i];
				idx=i;
			}
		}
		if(dasom>maxi)
		{
			cout<<count<<endl;
			break;
		}
		dasom++;
		v[idx]--;
		count++;
	}
	return 0;
}

다솜의 경우만 따로 입력을 받고 이후 투표수를 보면서 최댓값과 다솜의 값의 차이를 비교하며

만약 다솜이 아닌 사람의 투표수가 더 많은 경우에는 그 사람의 표를 1표 줄여 다솜의 표로 넣고 count를 높이며

다솜이 더 높은 경우에는 다른 사람들보다 무조건 높으므로 count를 출력하고 바로 종료합니다.

이 때 중요한 점은 가장 많은 투표수를 받은 사람과 한 번만 비교하게 되면 오답이 된다는 점입니다.

다솜의 투표 순위는 무조건 2등이 아니기 때문에 비교할 때 마다 최대 득표를 받은 사람을 새로 계산하고 비교해야 합니다.

반응형

'백준 문제풀이' 카테고리의 다른 글

1924번 : 2007년  (0) 2022.04.06
1546번 : 평균  (0) 2022.04.06
1427번 : 소트인사이드  (0) 2022.04.05
1032번 : 명령 프롬프트  (0) 2022.04.01
1026번: 보물  (0) 2022.04.01