c언어 1417번 국회의원 선거 (백준)

#include <stdio.h>

int main(void)
{
	int n = 0;
	int one = 0; //기호 1번 득표수
	int big = 0; //기호 1번을 제외한 가장 많은 득표수
	int arr[50] = {0}; //기호 2~51번 득표수
	scanf("%d", &n);
	scanf("%d", &one); //기호 1번 득표수
	
	int tmp = n--; //기호 1번 제외
	while(n--) { //나머지 
		scanf("%d", &arr[n]);
		if(big < arr[n]) big = arr[n]; //나머지들 중 가장 큰 거
	}
	
	if(one > big) { //만약 기호 1번 득표수가 가장 크면
		printf("0");
		return 0;
	}
	
	int ans = 0; //다른 기호 득표수가 더 많으면
	while(1) {
		int once = 0; //한명을 매수했는지?
		int top = 0; //한명을 매수한 후 나머지 기호 중 가장 많은 득표수
		for(int i=0; i<tmp; i++) {
			if(big == arr[i] && once == 0) { //한 명 매수
				ans++;
				one++;
				once++;
				arr[i]--;
			}
			if(top < arr[i]) top = arr[i]; 
		} big = top;
		if(one > big) break; //기호 1번이 가장 많으면 중단
	}
	printf("%d", ans); //몇 번 매수를 했는지 출력
    return 0;
}

 

 

풀이 

1) 모든 기호의 득표수를 입력받는다.

2) 기호 1번을 제외한 나머지 번호 들 중 가장 큰 득표수를 구한다.

3) 가장 큰 득표수보다 기호 1번이 더 많다면  매수한 사람들을 출력 후 종료

4) 3에서 종료가 안 될 경우, 기호 1번을 제외한 사람들 중 가장 많은 득표수를 가진 사람 중 1명을 매수하고, 다시 3)으로 간다.

     4-1) 가장 많은 득표수를 가진 사람 들 중 한 명을 매수 -> 기호 1번 득표수 1 증가, 매수당한 기호는 1 감소

     4-2) 1을 제외한 나머지 기호 중 가장 많은 득표수를 구함

     4-3)  3)의 과정을 다시 거침