[BaekJoon][2613] 숫자구슬

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2004

2613 숫자구슬

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

최대값의 최소값이라는 말을 보고 이진탐색이라고는 생각하였지만 처음에는 DP로 접근해 보았다.

DP로도 풀이가 생각났기 때문에..

dp[start][group] : start 지점부터 끝까지 group의 개수만큼 나누었을 때 그 합 중 최대값의 최소값을 저장

그룹 하나, sum값과 그 외의 구간을 group - 1개로 나누었을 때 나오는 최소값 중 최대값들 중에서 최소값을 저장해 나갔다.

그리고 저장해 나가면서 그 최소값이 되는 구간의 구슬 개수 또한 저장해 나갔다.

sum 값은 입력을 받으면서 이중 반복문으로 sum[start][end]에 미리 저장

시간은 4ms

#include <stdio.h>
 
#define Max(x, y)        (((x) > (y)) ? (x) : (y))
 
int n, m;
int sum[301][301];
int dp[301][301], count[301][301];
 
int solve(int start, int cnt)
{
    int i, temp, min = 987654321;
 
    if (cnt == 1) {
        count[start][cnt] = n - start + 1;
        return dp[start][cnt] = sum[start][n];
    }
    if (dp[start][cnt])    return dp[start][cnt];
    dp[start][cnt] = 987654321;
 
    for (i = start; i <= n - cnt + 1; i++) {
        temp = Max(sum[start][i], solve(i + 1, cnt - 1));
        if (temp < min) {
            min = temp;
            count[start][cnt] = i - start + 1;
        }
    }
 
    return dp[start][cnt] = min;
}
 
int main()
{
    int i, j, input;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &input);
        for (j = 1; j <= i; j++) {
            sum[j][i] += sum[j][i - 1] + input;
        }
    }
 
    printf("%d\n", solve(1, m));
    for (i = 1, j = m; j > 0; i += count[i][j], j--) {
        printf("%d ", count[i][j]);
    }
    printf("\n");
 
    return 0;
}

2. Binary Search

아무튼 이 문제는 최대값의 최소값을 찾는 문제로 Binary Search !!

정답이 될 값을 이진 탐색으로 찾아들어가며, 질답은 최대값이 middle 일 때 나눈 구간의 개수가 m보다 크면 left = middle + 1 부터, 나눈 구간의 개수가 m 이하이면 right = middle - 1로 답이 될 수 있는 구간 이동.

이 때, m으로 나눌 수 있을 때의 middle (정답 후보) 중 최소값이 최종 정답이다.

구슬의 개수는 질답할 때 구간 나누듯이 마지막에 한 번 더 출력

시간은 0ms

#include <stdio.h>
 
int n, m;
int input[301];
int ans;
 
int possible(int value)
{
    int i, sum, cnt;
 
    for (i = 0, sum = 0, cnt = 1; i < n - 1; i++) {
        sum += input[i];
        if (sum > value) {
            cnt++;
            sum = input[i];
        }
    }
    if (sum + input[i] > value)        cnt++;
 
    if (cnt <= m)    return 1;
    else    return 0;
}
 
void bsearch()
{
    int left = 0, right = n * 100, middle;
 
    ans = right;
    while (left <= right) {
        middle = (left + right) / 2;
        if (possible(middle)) {
            right = middle - 1;
            if (middle < ans)    ans = middle;
        }
        else    left = middle + 1;
    }
}
 
int main()
{
    int i, sum, cnt;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < n; i++)    scanf("%d", &input[i]);
 
    bsearch();
 
    printf("%d\n", ans);
 
    for (i = 0, sum = 0, cnt = 0; i < n; i++) {
        sum += input[i];
        if (sum > ans) {
            printf("%d ", cnt);
            sum = input[i];
            cnt = 0;
        }
        cnt++;
    }
    printf("%d\n", cnt);
 
    return 0;
}