글 읽기 - 알고리즘에 문제가 있을까요?

jnk98 8년 전 0

일단 제 풀이 방법을 간단히 설명 드리자면,

1. 길이 2L 이상인 해는 절대 존재하지 않는다.

왜냐하면, 길이 2L 인 해가 존재한다고 가정할 경우, 비둘기집이 원리(?) 에 의해 길이가 L이면서 평균이 더 크거나 같은 해가 항상 존재하기 떄문이다.

( 문제에서는 같은 평균일 경우 짧은 길이를 요구한다.)

2. 1.번에 의해 N번 루프를 돌리면서 L~2L-1 까지 전부 검사를 하면 좋지만, 10^8 루프이므로 시간 초과를 받을 것이 뻔하다.

그래서 제가 생각한 것이

1. 길이 L 인 평균값을 스캔해서 Max 가 나오는 지점을 전부 저장해 둔다. (여러개일 수 있으므로)

2. 1.번에서 구한 지점에서 좌우로(사실 우측만 해도 될 것 같기는 함) 영역을 2L 까지 늘리면서 2차 스캔을 한다.

입니다.

제가, 만든 테스트 케이스는 다 통과 되는데 , "틀렸습니다" 가 나오네요..ㅠ.ㅠ

질문 : 알고리즘이 잘못된걸까요? 아니면 생각 못한 특이 케이스가 있는걸까요?

// 1. 우선 길이 L인 윈도우로 스캐닝을 하면서 max 값이 나오는 지점을 전부 찾는다.
// 2. 1에서 나온 각 지점에서 좌우 방향으로 L 만큼씩 윈도우 사이즈를 키워가면서 2차 Scan을 한다. (L보다 더 크게 키우는 것은 작은 사이즈에서 더 큰 값이 존재한다는 뜻이므로 의미 없다. )
// 3. 1차에서 나온 max 값이 1이면 2차 스캔은 필요없다.
 
#include <stdio.h>
#include <stdlib.h>
 
char in[100005];
int max_start[100000];
 
 
int main()
{
    int T,N,L;
    int i,j,k,index,start,end;
    int res_start,res_end;
    float max,value;
    int num=0,max_index=0,max_cnt,num_backup;
 
    scanf("%d",&T);
 
    for(k=0;k<T;k++)
    {
 
        num=0;
        max_index=0;
 
        scanf("%d %d",&N,&L);
        scanf("%s",in);
 
     // first scan with fixed window L
 
        for(i=0;i<L;i++)
        {
            if(in[i]-'0') num++;
        }
        max_cnt=num;
        max_start[max_index]=0;
 
        for(i=1;i<=N-L;i++)
        {
            if(in[i+L-1]-'0') num++;
            if(in[i-1]-'0') num--;
 
            if(num > max_cnt)
            {
                max_index=0;
                max_cnt=num;
                max_start[max_index]=i;
            }
            else if(num == max_cnt)
            {
                max_index++;
                max_start[max_index]=i;
 
            }
        }
 
        res_start=max_start[0];
        res_end=res_start+L-1;
        max=(float)max_cnt/L;
  //      printf("max_cnt=%d\n",max_cnt);
 
    // second scan with extended window
 
        if(max!=1)
        {
            for(i=0;i<=max_index;i++)
            {
 
  //              max=(float)max_cnt/L;
                num=max_cnt;
                start=max_start[i];
                end=start+L-1;
 
                // left scan
                num_backup=num;
 
                for(j=1;j<=L-1;j++)
                {
                    index=max_start[i]-j;
                    if(index < 0) index=0;
                    else if(in[index]-'0') num++;
                    value=(float)num/(L+max_start[i]-index);
                    if(value>max)
                    {
 //                       printf("bingo!! %d %d \n",num,L+max_start[i]-index);
                        max=value;
                        res_start=index;
                        start=index;
                        res_end=end;
                        num_backup=num;
                    }
                }
 
                // right scan
                num=num_backup;
 
                for(j=1;j<=L-1;j++)
                {
                    index=max_start[i]+L-1+j;
                    if(index >= N) index=N-1;
                    else if(in[index]-'0') num++;
                    value=(float)num/(index-start+1);
                    if(value>max)
                    {
 //                       printf("bingo!! %d %d \n",num,(index-start+1));
                        max=value;
                        res_end=index;
                        res_start=start;
                    }
                }
 
            }
        }
 
     //   printf("num of max = %d\n",max_index);
 
        printf("%d %d\n",res_start+1,res_end+1);
    }
 
    return 0;
}

august14 8년 전 0

저 방법으로 길이가 같을 때는 시작 지점을 최대한 앞으로 해야한다는 조건이 만족되지 않을 것 같네요.

그리고 길이가 L인데 1의 개수가 최대인 구간의 개수가 매우 많을 수도 있지 않을까요?

jnk98 8년 전 0

저 방법으로 길이가 같을 때는 시작 지점을 최대한 앞으로 해야한다는 조건이 만족되지 않을 것 같네요.

=> Max 값을 이전 Max 값보다 커지는 경우에만 Update 하도록 함으로써 해결했다고 생각합니다.

그리고 길이가 L인데 1의 개수가 최대인 구간의 개수가 매우 많을 수도 있지 않을까요?

=> 그래서 배열에 저장해 놓고 각각의 케이스에 대해서 2차 스캐닝을 돌리도록 했습니다.

august14 8년 전 0

Max 값을 이전 Max 값보다 커지는 경우에만 Update 하도록 함으로써 해결했다고 생각합니다.

=> 그렇네요 제가 잘못 봤습니다. 문제는 그게 아니고 더 짧은 길이인 부분을 찾을 수 없다는 점이네요

그래서 배열에 저장해 놓고 각각의 케이스에 대해서 2차 스캐닝을 돌리도록 했습니다.

=> 그러면 N*L로 도는거랑 어떤 점이 다른 것인가요?

jnk98 8년 전 0

Max 값을 이전 Max 값보다 커지는 경우에만 Update 하도록 함으로써 해결했다고 생각합니다.

=> 그렇네요 제가 잘못 봤습니다. 문제는 그게 아니고 더 짧은 길이인 부분을 찾을 수 없다는 점이네요

=> L 이 최소 길이 이므로 더 짧은 경우는 생각할 필요가 없을 듯..

그래서 배열에 저장해 놓고 각각의 케이스에 대해서 2차 스캐닝을 돌리도록 했습니다.

=> 그러면 N*L로 도는거랑 어떤 점이 다른 것인가요?

=> 좋은 지적이십니다. 최악의 경우 N*L로 도는 알고리즘과 같아집니다.

그러나, 모든 수가 '1' 인 경우를 제외하고는 최악의 경우는 없다고 봤습니다. (제 생각일 뿐이지만 ^^)

그리고, 모든 수가 '1'이면 2차 스캔을 할 필요가 없습니다.

august14 8년 전 0

25 5

1100001100000000000110001

그리고 최악의 경우는 좀더 생각해보세요.. max_index가 N-L에 가깝게 나오는 경우가 있습니다.

jnk98 8년 전 0

25 5

1100001100000000000110001

위의 경우 소스코드에 넣어서 돌리면

1 8

이 나옵니다. 맞는거 아닌가요? (4/8 가 최대 값이 맞는거 같은데요..ㅠㅠ)

max_index가 N-L에 가깝게 나오는 경우에 대해서는 좀 더 생각해 보겠습니다. ^^

august14 8년 전 0

20 25입니다.

jnk98 8년 전 0

아~ 그렇네요.. 감사합니다.

틀린 원인이 뭔지 알겠네요..ㅋ

jnk98 8년 전 0

@august14 님이 제시하신 반례를 보고, 2차 스캔에서 length가 더 짧아지는 경우에 대해 고려해서 반례에 대해서는 해결을 했는데 그래도 "틀렸습니다" 가 나오네요.. 고려하지 못한 부분이 더 있는 듯..ㅠ.ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

알고리즘에 문제가 있을까요?

jnk98 8년 전 0

august14 8년 전 0

jnk98 8년 전 0

august14 8년 전 0

jnk98 8년 전 0

august14 8년 전 0

jnk98 8년 전 0

august14 8년 전 0

jnk98 8년 전 0

jnk98 8년 전 0

@august14 님이 제시하신 반례를 보고, 2차 스캔에서 length가 더 짧아지는 경우에 대해 고려해서 반례에 대해서는 해결을 했는데 그래도 "틀렸습니다" 가 나오네요.. 고려하지 못한 부분이 더 있는 듯..ㅠ.ㅠ

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말