글 읽기 - 9662 재질문입니다! ㅜㅜ

hananakajima 5년 전 0

우선 제가 코딩실력이 미천해서 깔끔하지 못하게 코딩한점 사과드립니다.

재귀함수+DP로 더 깔끔하게 표현할수있을거같은데 우선 지저분하게 메인함수에 다 때려넣었습니다.

돌을 가져갈수 있는 방법은 arr[0]~arr[K-1]에 저장 하고, 돌의 N마다의 승패는 sol[N]에 저장 (1,ㅡ0으로) 했습니다.

반복마디는 arr[K-1]+1번째 돌부터 반복이 발생할것이므로, 거기서부터 구하도록 했고 ,반복마디 값은 val에 저장시켰습니다.

손으로 몇가지 돌의갯수를 구해서 해본것하고 수동으로 맞춰보니 잘 맞는거같은데, 데이터세트 어디서 오답이 나는지 잘 모르겠습니다. ㅜㅜ

문제푸는 방법은 맞는거같은데....본좌님들의 혜안 부탁드립니다. ㅜㅜ

(이전답변 yukariko님 감사했습니다~!)

#include <stdio.h>

int main()
{
    int num,i,j,M,K,temp,test,val=1,count=0,total=0;
    int arr[22];
    int sol[2000];
    scanf("%d %d",&M,&K);
    
    for(i=0;i<2000;i++)
     sol[i]=0;

    for(i=0;i<K;i++){
     scanf("%d",&arr[i]);
     sol[arr[i]]=1;
    }

    for(i=arr[0]+1;i<2000;i++){
      if(sol[i]==0){
        j=0;
        test=1;
        while(i>arr[j]){
          test*=sol[i-arr[j]];  
          j++;
          if(j>=K)
          break;

        }
        if(test==0)
        sol[i]=1;
        else
        sol[i]=0;
      }     
    }
    
   for(i=arr[K-1]+1;i<999;i++){
      test=1;
     for(j=arr[K-1]+1;j<=arr[K-1]+i;j++){
       if(sol[j]==sol[j+i])
         test*=1;
       else
         test*=0;
     }
      if(test==1){
       val=i;
       break;
       }
   }
   
if(M>arr[K-1]){
for(i=1;i<=arr[K-1];i++){
    if(sol[i]==0)
      total++;
      }
      
   for(i=arr[K-1]+1;i<=arr[K-1]+val;i++){
    if(sol[i]==0)
      count++;
}
 total+= ((M-arr[K-1])/val)*count;
  for(i=arr[K-1]+1;i<=arr[K-1]+((M-arr[K-1])%val);i++){
       if(sol[i]==0)
       total++;
       }
  }
 else
for(i=1;i<=M;i++){
    if(sol[i]==0)
      total++;
      }      

printf("%d",total);

     
    return 0;
    
}

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

문제

문제

출처

ICPC

9662 재질문입니다! ㅜㅜ

hananakajima 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말