문제 링크

접근 방식

• 처음에는 어떤 방식으로 풀어야되지? 잘 모르겠어서 코드부터 써봤는데 알고보니 구현문제여서 그럴 수 밖에 없었다.
• n, dasom까지 받고 나머지를 배열로 받아 계속 Array.sorts하면서 비교했다.
• Array.sorts를 하면 내림차순으로 되는 줄 알고.. 있었는데 출력해보니 오름차순으로 정렬된다는 점을 알았다.

내 코드 & 개선할 점

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1417_국회의원선거_S5 {
    static int n, m;
    static int result = 0;
    static int dasom;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dasom = Integer.parseInt(br.readLine());

        if (n > 1) {
            arr = new int[n - 1];
            for (int i = 0; i < n - 1; i++)
                arr[i] = Integer.parseInt(br.readLine());

            while (true) {
                if (dasom <= arr[n - 2]) {
                    arr[n - 2]--;
                    dasom++;
                    result++;
                } else if (dasom > arr[n - 2])
                    break;
            }
        }

        System.out.println(result);
    }
}

• S5 정도는 혼자 10분 내로 수월하게 풀 수 있는 정도인 것 같다. 그래서 더 시간이 짧은 다른 코드들을 참고했고 매번 돌면서 Arrays.sort가 실행되는 게 느리다는 것을 알게 되었다.

개선된 코드

import java.io.*;
import java.util.*;
public class Main {


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

        int num = 0;
        int vote = input[0];
        int answer=0;

        while(true){

            for (int i = 0; i < N; i++) {
                if(input[i] >= vote){
                    num = i;
                    vote = input[i];
                }
            }

            if(num == 0) break;

            input[0]++;
            input[num]--;
            answer++;
ㅐ
            vote = -1;
        }

        System.out.println(answer);
    }
}

---

가장 득표 많은 사람 찾기

for (int i = 0; i < N; i++) {
    if(input[i] >= vote){
        num = i;
        vote = input[i];
    }
}

• 전체 후보의 득표를 훑어서(0 ~ N-1)

• vote보다 크거나 같으면, ㅐ
  이 루프가 끝나면:

• num → 가장 득표 높은 후보의 index

• vote → 그 후보의 득표수

---

다솜이 1등이면 종료

if(num == 0) break;

• num == 0 이면 1등이 다솜이므로 더 이상 뺏을 필요 없음.

---

다솜이 1등이 아니면 표 한 표 뺏어오기

input[0]++;     // 다솜 표 +1
input[num]--;   // 가장 강한 경쟁자 표 -1
answer++;       // 매수 횟수 증가

즉, 가장 위험한 경쟁자에게서 표를 뺏어서 다솜에게 줌*

---

다음 반복 준비

vote = -1;

• vote = -1 로 초기화해서 다음 for문에서 정상적으로 갱신되도록 함

---

1. 매 반복마다 “현재 최고 득표자”를 찾고
2. 그 사람에게서 표를 1개 가져와서 다솜에게 줘서
3. 다솜이 가장 높은 득표를 얻을 때까지 반복

즉, 다솜이 확실히 1등이 될 때까지 최소 횟수로 표를 훔치는 그리디 알고리즘.