백준 2512번 - 예산 (이분탐색) 질문드립니다! about fastcampus

[eastheat10]

감사합니다!! 덕분에 해결했습니다ㅠㅠ

[rhs0266]

첫 번째 질문자님 안녕하세요!

네 맞습니다. 해당 문제 정답 코드를 보시면, determination(limit) 이라는 함수에서 "limit이란 가격으로 맞춰 줄 수 있느냐" 라는 질문에 대답을 계산할 때 Math.min(A[i], limit) 을 누적해주죠? 이 때, limit이 무한대여서 모두가 자기가 원하는 만큼 전부 받을 수 있을 때, 실제로 사람들이 무한대까지 돈을 받지 않아도 함수가 True를 돌려주게 됩니다.

문제가 원하는 정답은 배정된 예산들 중 최댓값인 정수를 출력한다. 이기 때문에 실제 받는 돈의 범위에서 구하고자 Max를 취했습니다!

좀 더 직관적인 반례를 드리겠습니다.

1
1
1000000000

이러면 어떻게 실행되는 지 확인해보시겠나요?

[eastheat10]

감사합니다!!

그리고 2343 - 기타레슨과 6236 - 용돈관리 이 두 문제가 비슷해서 같은 내용에 대해 질문이 있습니다.

처음 L과 R을 설정할 때 L을 주어진 배열에서 최댓값으로 설정하는데, 오름차순 정렬을 하고 L에 A[n]을 입력하면 두 문제 다 틀렸다고 결과가 나옵니다. 혹시 왜 이런지 알 수 있을까요?

1300번 - K번째 수 solution.java 코드가 17266번 - 어두운 굴다리 코드로 대신 올라간 것 같습니다 .

[rhs0266]

감사합니다!!

그리고 2343 - 기타레슨과 6236 - 용돈관리 이 두 문제가 비슷해서 같은 내용에 대해 질문이 있습니다.

처음 L과 R을 설정할 때 L을 주어진 배열에서 최댓값으로 설정하는데, 오름차순 정렬을 하고 L에 A[n]을 입력하면 두 문제 다 틀렸다고 결과가 나옵니다. 혹시 왜 이런지 알 수 있을까요?

1300번 - K번째 수 solution.java 코드가 17266번 - 어두운 굴다리 코드로 대신 올라간 것 같습니다 .

@eastheat10 코드를 주시면 봐드릴게요 ㅎㅎ

코드 수정했습니다 감사합니다.

[eastheat10]

2343번 - 기타레슨입니다.

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

// 기타레슨
public class Main {

    static int n, m;
    static int[] arr;

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, 1, n + 1);
    }

    static boolean check(int size) {
        int count = 1;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (sum + arr[i] > size) {
                count++;
                sum = arr[i];
            } else {
                sum += arr[i];
            }
        }
        return count <= m;
    }

    static void process() {
        int l = arr[n];
        int r = 1000000000;
        int answer = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                answer = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

6236번 - 용돈관리입니다.

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

// 용돈 관리
public class Main {

    static int n, m;
    static int[] arr;

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n + 1];
        for (int i = 1; i <= n; i++)
            arr[i] = Integer.parseInt(br.readLine());
    }

    static boolean check(int l) {
        int count = 1;
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += arr[i];
            if(sum > l) {
                count++;
                sum = arr[i];
            }
        }

        return count <= m;
    }

    static void process() {
        Arrays.sort(arr, 1, n + 1);
        int l = arr[n];
        int r = arr[n] * m;
        int answer = 0;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                answer = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }

}

두 문제 다 l을 선언할 때 배열 arr의 최댓값을 대입해서 arr정렬 후 arr[n]을 l 에 대입하면 오답이 나오네요...

[rhs0266]

@eastheat10 두 문제 모두 입력을 정렬하면 문제에서 요구한 설명을 전혀 만족시키지 못합니다. 순서가 중요한 문제에서는 정렬을 주의해주세요. L 값을 최댓값으로 잡아도 정답에는 문제가 없지만, 순서가 바뀌어서 문제인 것입니다. 단순히 최댓값을 구하는 건 정렬 안 하고 찾는 게 더 빠르기도 하구요.

[rhs0266]