목걸이 문제

11.목걸이 문제

당신은 n(n≤40)개의 구슬로 만든 목걸이를 가지고 있는데, 구슬은 붉은색, 푸른색, 흰색의 세가지 색 중 하나이다. 예를 들어 다음과 같은 목걸이가 있을 수 있다.

brbrrrbbwrrwwbbbrrrrwwb

b,r,w는 각각 푸른색(blue), 붉은색(red), 흰색(white) 구슬을 나타낸다. 목걸이는 원형으로 연결되어 있으므로 맨앞의 b와 맨끝의 b는 연결되어 있으며, 또한

wbbbrrrrwwb,brbrrrbbwrrw라고 표현해도 위의 것과 똑같은 목걸이를 나타낸다.

목걸이의 한 군데를 끊어서 직선으로 늘어 놓을 때 앞쪽에서 시작해서 똑같은 색깔이 계속되는 구슬과 뒤쪽에서 시작해서 똑같은 색깔이 계속되는 구슬을 모으고자 한다. (앞에서 시작해서 계속되는 구슬의 색과 뒤에서부터 시작해서 계속되는 구슬의 색이 같은 필요는 없다)

특이한 점은 흰색 구슬은 우리가 필효할 때 붉은 색, 푸른색 어느 색이라도 칠할 수 있다는 것이다.( 그러나 흰색 구슬에 색을 칠하지 않고 그대로 두어서는 안된다. 즉, 구슬을 모을 때 흰색 구슬은 다른 두 색중 반드시 어느 하나로 취급된다)

예를 들어 위의 목걸이는 24,25번째 사이를 끊으면 아래와 같이 되어 11개를 모을 수 있다.

rrrrwwbbrbrrrbbwrrwwbbb

앞에서부터 모은 구슬과 뒤에서부터 모은 구슬의 개수의 합이 최대가 되게 하려면 어느 곳을 끊어야 하는지, 그리고 이 때 구슬을 최대 몇 개 모을 수 있는지 출력하는 프로그램을 작성하라.

실행 예)

Input a necklace : brbrrrbbbrrrrrbrrbbrbbbbrrrrb

8. between 9 and 10

// 9와 10 사이를 끊으면 8개를 모을 수 있다.

Input a necklace : bbwbrrrwbrbrrrrrb

10. between 16 and 17

소스

#include<stdio.h>
#include<string.h>
#define MAX 400
int getbead(int);
int left(int);
int right(int);
int n,neck[MAX];
int max,wherecut;
void inputdata()
{
    FILE *fp=fopen("input.txt","r");
    int q;
    char temp[MAX];
    
    fscanf(fp,"%s", temp);
    n=strlen(temp);
    for(q=1;q<=n;q++)
    {
        if(temp[q-1]=='b')
            neck[q]=1;
        else if(temp[q-1]=='r')
            neck[q]=2;
    }
}
void process()
{
    int q,w;

    for(q=1;q<=n;q++)
    {
        w=getbead(q);
        if(max<w)
        {
            max=w;
            wherecut=q;
        }
    }
}
int getbead(int what)
{
    int lt, rt;
    
    rt = right( (what%n) + 1);
    lt = left(what);
    if(rt+lt>n) return n;
    return lt+rt;
}
int left(int what)
{
    int i=what,count=0;
    int ch[3]={0,0,0};
    
    for(;;)
    {
        ch[neck[i]]=1;
        if(ch[1]!=0 && ch[2]!=0) return count;
        i--;
        count++;
        if(i==0) i=n;
        if(i==what)    return n;
    }
    return -1;
}
int right(int what)
{
    int i=what;
    int count=0;
    int ch[3]={0,0,0};
    for(;;)
    {
        ch[neck[i]]=1;
        if(ch[1]!=0 && ch[2]!=0) return count;
        i++;
        count++;
        if(i==n+1) i=1;
        if(i==what) return n;
    }
    return -1;
}
void outputdata()
{    
    printf("%d between %d and %d\n", max, wherecut, wherecut%n+1);
}
void main()
{
    inputdata();
    process();
    outputdata();
}