[백준] 14627번. 파닭파닭(JAVA)

문제

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

---

풀이(22분)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken()); // 파의 개수
        int c = Integer.parseInt(st.nextToken()); // 주문 받은 파닭 수

        int[] greenOnions = new int[s];
        long totalSum = 0;

        for (int i = 0; i < s; i++) {
            greenOnions[i] = Integer.parseInt(br.readLine());
            totalSum += greenOnions[i];
        }

        Arrays.sort(greenOnions);

        long min = 1;
        long max = greenOnions[s - 1]; // 최댓값으로 변경
        long length = 0;

        // 이분 탐색
        while (min <= max) {
            long mid = (min + max) / 2;
            long count = 0;

            for (int i = 0; i < s; i++) {
                count += greenOnions[i] / mid;
            }

            if (count >= c) {
                length = mid;
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }

        // 남은 파 계산 (총 길이 - 사용된 길이)
        long used = length * c;
        long answer = totalSum - used;

        System.out.println(answer);
    }
}

---

문제 풀이 전략

 

이분탐색을 통해 파의 길이를 정한 뒤 정답을 도출해 내야겠다는 것은 어렵지 않게 떠올릴 수 있었다.

 

다만 문제는 정답을 도출하는 과정이었기 때문에 이 부분에 초점을 맞추어서 적어두어야겠다.

 

다른 문제에서도 충분히 나올 수 있을법한 실수일 것 같은데 단순한 최종 연산자 선택이다.

필자 같은 경우 처음에 legnth를 구한 뒤 배열을 순회하며 나머지 연산으로 직접 answer을 하나씩 추가해 나갔다.

하지만 이 경우 어떤 문제가 발생할 수 있는지 예상이 되는가? -> 사실 필자도 반례를 보기 전까지는 전혀 생각하지 못했다.

문제에서 제시된 예시를 먼저 보자.

3 5
440
350
230

이 경우 length 가 175로 잡힌다. 그렇다면

440 % 175 = 90

350 % 175 = 0

230 % 175 = 55로 정답인 145가 제대로 도출된다.

 

 

반례의 경우

3 5
10
10
10

이라는 입력이 주어졌다고 하자.

length가 5로 잡힌다. 그렇다면

10 % 5 = 0이 반복되며 정답이 0이 출력된다.

실제 정답은 총 5개의 파를 만들어야 하기에 2개 2개 1개로 5가 남아야 한다.

 

결과적으로 나머지 연산이 적절하지 않았다는 것이다.