[Algo] 백준 24913 개표 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/24913

메모리 : 99204KB

시간 : 656ms

언어 : Java 11

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 후보
        int Q = Integer.parseInt(st.nextToken()); // 개표
        long[] person = new long[N + 2];
        StringBuilder sb = new StringBuilder();
        long sum = 0;
        long max = 0;
        for (int q = 0; q < Q; q++) {
            st = new StringTokenizer(br.readLine());
            int order = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if (order == 1) {
                person[y] += x;
                if (y != N + 1) {
                    sum += x;
                    max = Math.max(max, person[y]);
                }
            } else {
                long jung = person[N + 1] + x;
                long tmp = (sum + y) / N;
                if ((sum + y) % N != 0) {
                    tmp += 1;
                }
                if (jung <= max) {
                    sb.append("NO").append("\n");
                } else if (jung <= tmp) {
                    sb.append("NO").append("\n");
                } else {
                    sb.append("YES").append("\n");
                }
            }
        }
        System.out.print(sb);
    }
}

풀이

맨 처음에 당선이 될 수 있는 경우를 찾으려했는데ㅜㅜ 너무 복잡했다..
당선이 되지 않는 경우를 생각해서 구현하면 더 쉬웠다.

1. 1~N번의 후보보다 정후의 득표가 높은 경우
2. 추가표를 나눠가져도 정후의 득표가 높은 경우
   • 추가표를 최소로 얻는 경우는 (1~N까지의 득표 합+추가표) / N 이다.