[BOJ 1417/ C++] 국회의원 선거

문제 링크

문제에 대한 사항은 위의 링크로 확인할 수 있다.

해결 방안

• 다솜이의 표를 가장 먼저 입력받으므로 다솜이의 표 이후의 값 중 최댓값을 찾아 다솜이의 값을 올리고(+=1) 해당 값을 내린다.(-=1)

• 위와 같은 동작을 다솜이의 표가 이후의 값 중 최댓값보다 높을 때까지 반복한다.

코드

#include <iostream>

using namespace std;

int N, fidx, re = 0;
int c[50] = { 0, };

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> c[i];
	}

	if (N == 1) {  // N==1이면 매수할 필요 없다.
		cout << 0;
		return 0;
	}

	int maxn = -1;

	while (1) {
		for (int i = 1; i < N; i++) {  // 0번째 인덱스에는 다솜이의 표가 있으므로 1부터 max값을 찾는다.
			if (maxn <= c[i]) {
				maxn = c[i];
				fidx = i;  // max값의 index
			}
		}

		if (maxn >= c[0]) {
			c[fidx]--;
			maxn = -1;  // 나의 표수를 올린 후 다시 처음부터 max값을 찾아야 하므로
			c[0]++;
			re++;
		}
		else
			break;
		
	}


	cout << re << endl;

	return 0;
}

다른 해결 방안들

• 정렬을 이용한다.
  • (1) 다솜이 이후의 값들을 최댓값이 맨앞으로 오게 정렬을 한다.
  • (2) 맨 앞 값과 다솜이 값 간의 계산을 한다.
  • (3) 위 과정을 다솜이 값이 최대가 되도록 반복한다.