[BOJ #2613] 숫자구슬

숫자구슬은 Parametric Search 를 알고 계셨다면 쉽게 풀으셨을겁니다. 이분 탐색을 이용하여 결정 문제를 해결하는 기법이에요.

---

[Baekjoon Onine Judge]

#2613 숫자구슬

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

2004 한국정보올림피아드 시.도지역본선 고등부 4번

---

Problem Solving Strategy

Parametric Search에 대해 알고 있거나, 이분탐색이나 나무자르기 같은 문제를 풀어보았으면 바로 떠오를 것입니다. ^=^

어쨌든 Parametric Search로 문제를 풀어봅시다.

1. 무엇을 이분탐색할 것인가?

범위로 주어진 것이 정답의 범위밖에 없으니까 정답의 범위를 이분탐색 해봅시다.

N은 300이하이고, 구슬의 숫자는 100이하이므로 정답의 범위는 30000이하이겠죠?

left는 1로 right는 30000으로 잡아줍시다.

int left=1,right=(100*N);

2. 어떻게 판단할 것인가?

어떨 때 왼쪽으로 가고, 어떨 때 오른쪽으로 갈까요?

보통 문제의 조건에서 판단의 기준이 찾아져요.

이 문제에서 수치화된 조건은 그룹의 개수, 정답인 그룹의 구슬의 개수가 있네요.

아무래도 전자가 끌리죠?

답(mid)이 정해지면, 최소 그룹의 개수도 정해집니다.

How?

처음 구슬부터 시작해서 구슬의 합이 mid를 넘지 않을 때까지 한 그룹으로 묶어주면 되기 때문입니다.

for(int i=0;i<N;i++){
    sum+=marble[i];
    if(sum>mid){
        countGroup++;
        sum=marble[i];
    }
}

그러면 구슬의 합이 mid를 넘지 않는 경우 그룹의 최대 개수가 정해집니다.

그룹의 최소 개수가 M보다 크면 정답이 아니죠? 오른쪽을 탐색해나갑니다.

작으면 그룹을 분할하여 M개가 될 수도 있으니, 일단 기존의 answer과 비교하여 mid가 더 작을 경우 answer를 mid로 바꾸고 왼쪽을 탐색해나갑니다.

if(countGroup>M) left=(mid+1);
else{
    right=(mid-1);
    if(mid<ans) ans=mid;
}

---

틀리기 쉬운 부분

사실 이 부분은 어떻게 풀었고, 어떻게 구현했는가에 따라서 각자 다른 오답노트를 작성하게 되겠지만, 제 경우입니다.

3. 만약에, 구슬이 mid보다 클 경우에는?

저격데이터라 부르기도 민망한 케이스죠. 제가 걸렸으니까 포스팅에 넣어봅니다ㅋㅋㅋ

이경우 탐색은 무조건 오른쪽이니까, 아까 2번 과정의 첫 번째 코드에 있는 for문 안에 다음과 같은 if문을 넣어 해당 케이스를 표기합니다.

if(marble[i]>mid){
    left=mid+1;
    boolean=0;
    break;
}

그리고 두 번째 코드에서 if(오른쪽을 탐색할 것인가)에 오른쪽을 탐색한다!라고 명령합니다.

if(countGroup>M || boolean==0) (left=mid+1);

뭐 다양한 해결방법이 있겠지만 저는 위처럼 해결했습니다.

그리고...

꽤나 (제가) 찾기 어려웠던 케이스인 아래 상황을 소개합니다!

4. 한 그룹에는 하나 이상의 구슬이 있어야 한다

이렇게 들으니 감이 잘 안 올거에요. 이게 왜 저격 데이터야? 묻는 사람이 있을 겁니다.

보통 코드 구현 과정에서 각 그룹을 구성하는 구슬의 개수를 출력할 때, 이진탐색을 도는 과정에서 저장을 하거나, 이진탐색에서의 코드를 아래에 복붙한 뒤, mid만 answer로 바꾸어서 출력을 합니다.

그리고 맞았습니다가 뜨기를 기도하며 제출을 하지만

결과는 틀렸습니다.

네. 저도 그랬습니다 ㅋㅋㅋ캬캬ㅏ

문제를 잘 읽어보면 최대값과 각 그룹을 구성하는 구슬의 개수를 출력해야합니다.

현재 mid가 2일 때 

4 2

1 1 2 1 이라고 입력해봅시다.

그러면 그룹 분류가 다음과 같이 됩니다.

(1,1) (2) (1)

그럼 그룹의 구슬 개수를 출력이 다음처럼 나오겠죠?

2 1 1

넵. 틀렸습니다.

결과를 출력하기 전에

세어진 그룹의 개수와 M을 비교한 뒤

부족한 그룹의 개수만큼

중간에 구슬의 개수가 2개 이상인 그룹을 분할해서 해결해줍시다.

int num=0,sum=0;
for(int i=0;i<N;i++){
    sum+=marble[i];
    num++;
    if(sum>ans){
        sum=marble[i];
        answer[ansSize]=num-1;
        ansSize++;
        num=1;
    }
}
answer[ansSize]=num;
int difference=(M-ansSize); //M과 ansSize의 차이를 계산한다.
for(int i=1;i<=ansSize;i++){
    if(answer[i]==1) printf("%d ",answer[i]);
    else{
        while(answer[i]>=2 && difference>=1){
            printf("1 ");
            answer[i]--; difference--;
        }
        printf("%d ",answer[i]);
    }
}

---

전체 코드 보기

#include<cstdio>
int N,M,marble[302];
int answer[301],ansSize=1;
int main(void){
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&marble[i]);
    int left=1,right=(100*N);
    int ans=999;
    while(left<=right){
        int mid=(left+right)/2;
        int sum=0,countGroup=1;
        bool boolean=1;
        for(int i=0;i<N;i++){
            if(marble[i]>mid){
                left=mid+1;
                boolean=0;
                break;
            }
            sum+=marble[i];
            if(sum>mid){
                countGroup++;
                sum=marble[i];
            }
        }
        if(countGroup>M || boolean==0) (left=mid+1);
        else{
            right=(mid-1);
            if(mid<ans) ans=mid;
        }
    }
    printf("%d\n",ans);
    int num=0,sum=0;
    for(int i=0;i<N;i++){
        sum+=marble[i];
        num++;
        if(sum>ans){
            sum=marble[i];
            answer[ansSize]=num-1;
            ansSize++;
            num=1;
        }
    }
    answer[ansSize]=num;
    int difference=(M-ansSize);
    for(int i=1;i<=ansSize;i++){
        if(answer[i]==1) printf("%d ",answer[i]);
        else{
            while(answer[i]>=2 && difference>=1){
                printf("1 ");
                answer[i]--; difference--;
            }
            printf("%d ",answer[i]);
        }
    }
}