숫자구슬은 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으로 잡아줍시다.


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



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

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

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

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

아무래도 전자가 끌리죠?


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

How?

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


1
2
3
4
5
6
7
for(int i=0;i<N;i++){
    sum+=marble[i];
    if(sum>mid){
        countGroup++;
        sum=marble[i];
    }
}
cs


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

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

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


1
2
3
4
5
if(countGroup>M) left=(mid+1);
else{
    right=(mid-1);
    if(mid<ans) ans=mid;
}
cs


틀리기 쉬운 부분


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

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

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

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


1
2
3
4
5
if(marble[i]>mid){
    left=mid+1;
    boolean=0;
    break;
}
cs


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


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


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


그리고...

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


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

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


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

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

결과는 틀렸습니다.

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


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


현재 mid가 2일 때 


4 2

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


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

(1,1) (2) (1)

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

2 1 1

넵. 틀렸습니다.


결과를 출력하기 전에

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

부족한 그룹의 개수만큼

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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]);
    }
}
cs


전체 코드 보기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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]);
        }
    }
}

cs



네엡! Parametric Search가 이런 거에요 *-*

사실 Parametric Search라는 용어보다는 관련문제인 #2805 나무자르기가 더 유명한데, 이 문제도 풀어보면 좋아요.


지역본선은 정말 문제를 보고 기초 알고리즘을 떠올릴 수 있으면 풀 수 있는 문제가 대부분이에요 

그래도 꼼꼼하지 않으면, 저처럼 몇 번씩 틀립니다ㅠ-ㅠ

'Algorithm > BOJ 문제풀이' 카테고리의 다른 글

[BOJ #1406] 에디터  (0) 2019.03.26
[BOJ #2594] 놀이공원  (0) 2018.02.14
[BOJ #2610] 회의준비  (0) 2018.02.12

시.도지역본선 초반 번호대의 문제다운 난이도로, Floyd-Warshall Algorithm (플로이드 와샬)을 이용해, 간단히 해결되는 문제입니다.


[Baekjoon Onine Judge]


#2610 회의준비


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


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

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

Problem Solving Strategy


다음과 같은 세 부분으로 나누어 생각을 해야지! 라는 생각이 떠오를 것입니다.

1. 모든 사람에 대해 플로이드 와샬 알고리즘을 돌린다.

2. 조건에 맞게 위원회를 구성한다.

3. 위원회의 대표를 찾는다.


1. 모든 사람에 대해 플로이드 와샬 알고리즘을 돌린다.

위원회의 대표를 찾는 과정에서, 플루이드 와샬 알고리즘이 필요하다는 것은 깨달았을 것입니다.

각각의 위원회에 대해 돌려도 되지만 코드가 불필요하게 길어지며, 모든 사람이 같은 위원회에 속하는 경우의 수도 존재하므로

처음에 그냥 모든 정점을 집어넣고 돌립니다.


1
2
3
4
for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(i!=j && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];
cs


2. 조건에 맞게 위원회를 구성한다.

3. 위원회의 대표를 찾는다.

굳이 각 위원회의 정보를 저장할 필요가 없으므로,  imsi로 그룹원을 저장하는 배열을 만들고 대표를 찾은 뒤, 각 그룹의 대표만 저장해도 됩니다. 본인은 반복문 탈출 조건을 N명의 사람을 모두 방문했을 때로 했습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vSize=0; aSize=0;
while(vSize<N){ //방문한 사람 수가 N보다 작은 동안 반복문을 돕니다.
//임시 위원회를 구하는 과정입니다.
    emptyImsi();
    for(int i=1;i<=N;i++){
        if(imsisize==0 && visited[i]==0){ //임시 위원회의 한 사람을 구합니다.
            visited[i]=1; //방문자 처리
            imsisize++; vSize++;
            imsi[imsisize]=i;
            e=i;
        }
        if(imsisize!=0 && dist[e][i]!=INF){ //임시 위원회의 나머지 그룹원을 채워줍니다.
            visited[i]=1;
            imsisize++; vSize++;
            imsi[imsisize]=i;
        }
    }
 
//위원회의 대표를 찾는 과정입니다.
    s=1;//s는 일단 위원회의 1번을 대표라 가정합니다.
    int pe=INF;
    for(int i=1;i<=imsisize;i++)
    {    
        e=0;
        for(int j=1;j<=imsisize;j++)
        {
            if(e<=dist[imsi[i]][imsi[j]] && i!=j){
                e=dist[imsi[i]][imsi[j]];
            }
        }
        if(pe>=e){
            s=i;
            pe=e;
        }
    }
    aSize++; //출력할 답의 크기를 저장합니다.
    ans[aSize]=imsi[s]; //출력에 필요한 답만 저장해둡니다.
}
cs

전체 코드 보기


블로그에 정리할 생각을 하지 않고 짰던 거라 변수명과 코드가 조금 지저분..해요 ㅠ-ㅠ


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<algorithm>
#define INF 987654321
using namespace std;
 
int N, dist[101][101];
int imsi[101],imsisize,visited[101],vSize;
int M,s,e;
int ans[101],aSize;
 
void emptyImsi(){
    for(int i=1;i<=N;i++) imsi[i]=0;
    imsisize=0;
}
 
int main(void){
    imsisize=0;
    scanf("%d",&N);
    scanf("%d",&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            dist[i][j]=INF;
    for(int i=1;i<=M;i++){
        scanf("%d %d",&s,&e);
        dist[s][e]=1; dist[e][s]=1;
    }
 
    //fw algorithm//
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
            if(i!=j && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];
 
    vSize=0; aSize=0;
    while(vSize<N){
    //임시 부분집합을 구하고
        emptyImsi();
        for(int i=1;i<=N;i++){
            if(imsisize!=0 && dist[e][i]!=INF){
                visited[i]=1;
                imsisize++; vSize++;
                imsi[imsisize]=i;
            }
            if(imsisize==0 && visited[i]==0) {
                visited[i]=1;
                imsisize++; vSize++;
                imsi[imsisize]=i;
                e=i;
            }
        }
        
    //부분그룹의 대표를 찾는다.
        s=1;//s는 일단 부분그룹 1번이 대표!
        int pe=INF;
        for(int i=1;i<=imsisize;i++)
        {    
            e=0; //s는 임시 그룹 1번 여기서부터 e=MAX
            for(int j=1;j<=imsisize;j++)
            {
                if(e<=dist[imsi[i]][imsi[j]] && i!=j){
                    e=dist[imsi[i]][imsi[j]];
                }
            }
            if(pe>=e){
                s=i;
                pe=e;
            }
        }
        aSize++;
        ans[aSize]=imsi[s];
    }
    sort(ans+1,ans+1+aSize);
    printf("%d\n",aSize);
    for(int i=1;i<=aSize;i++)
        printf("%d\n",ans[i]);
    return 0;
}




'Algorithm > BOJ 문제풀이' 카테고리의 다른 글

[BOJ #1406] 에디터  (0) 2019.03.26
[BOJ #2594] 놀이공원  (0) 2018.02.14
[BOJ #2613] 숫자구슬  (4) 2018.02.13

+ Recent posts

티스토리툴바