DRAGON 질문드립니다!!

  • kws4679
    kws4679

    우선 저는 다음과 같은 방법으로 풀었습니다.

    n세대는 x(n-1) + y(n-1) 이므로

    x(n-1) 의 개수를 구한다음에

    구하고자하는 것이 x(n-1)범위에 들어가면 재귀호출
    x(n-1) 에서 y(n-1) 까지 걸친다면
    x(n-1) 재귀호출과 +,- 출력 그다음에 y(n-1) 재귀호출
    만일 y(n-1) 범위에 들어가면 y(n-1) 에 대해서 재귀호출

    이런식으로 하였습니다.

    #include <iostream>
#include <cstring>
using namespace std; 
const int MAX = 1000000000+100;
int cache[51];
int x(int n){
    if(!n) return 2;

    int& ret = cache[n];
    if(ret != -1) return ret; 
    return ret = min(2*x(n-1)+1,MAX);
}
void dragon(int n, int p, int l, int w){
    // w == 1 then Y, 0 then X
    if(!n){
        printf("%s", string(!w?"FX":"YF").substr(p-1,p+l-1).c_str());
        return; 
    }    

    int left = x(n-1);
    if(p+l <= left) dragon(n-1,p,l,0);
    else if(p <= left+1 && left+1 <= p+l){
        if(p<left+1) dragon(n-1,p,left-p+1,0);
        printf(!w?"+":"-");
        if(left+1<p+l) dragon(n-1,1,p+l-left-2,1);
    } else if(p>left+1) dragon(n-1, p-left-1,l, 1);
}

int main(){
    int c;
    scanf("%d", &c); 
    while(c--){
        memset(cache, -1, sizeof(cache));
        int n,p,l;
        scanf("%d %d %d", &n, &p, &l); 
        dragon(n, p, l, 0);
    }    
    return 0;
}

    그런데 자꾸 오류라고 뜨는데 어떻게 반례를 찾아야할지 감이안오네요 ㅠㅠ


    11년 전
5개의 댓글이 있습니다.
  • kws4679
    kws4679

    더불어 요새 오류가 떠서 해결하지 못한 경우가 많습니다.

    혹시 체계적으로 오류 및 반례를 찾을수있는 방법은 없을까요?

    일반적인 경우에 랜덤테스트케이스를 생성한다지만 이런경우에는

    상당히 애매하네요 ㅠㅠ 도움 부탁드립니다!!


    11년 전 link
  • VOCList
    VOCList

    DRAGON 문제소환


    11년 전 link
  • VOCList
    VOCList

    문제 전에 먼저 오류 검증 방안부터 말씀드리자면, 제 생각엔 많이 풀어보시고 많이 경험하면서 빠짐없는 논리를 쌓는 연습을 하는 것이 결국 내 경험이 되고 남는 방법이 아닌가 해요. 제가 딱히 오류 및 반례에 대해서 체계적으로 공부해 본 경험이 없어서 그런 것일지도 모르겠지만 이거이거이거만 딱 보면 된다 하는 가이드라인을 찾기 정말 힘든 부분이기도 해서요. 굳이 찾자면 대회 후기나 다른 사람의 실수모음같은 글을 읽어보는 정도.. 말곤 전 딱히 생각나지 않네요.

    더 좋은 방안이 있으시면 아랫분이 :) 저도 많이 궁금하네요.


    11년 전 link
  • kws4679
    kws4679

    오오 빠른답변감사합니다 저도 많이궁금하네요 ^^ 결국에는 랜덤케이스 생성으로 테스트해봐서 해결은 했습니다만 사실 언제까지 랜덤으로 생성하고있을수도 없는 노릇이고 ㅠㅠ


    11년 전 link
  • JongMan
    JongMan

    이 문제 같은 경우엔 느리지만 간단한 해법(하나하나 직접 생성)이 있기 때문에 이걸 짜보고 비교해 보시면 어떨까요. 물론 시간은 오래 걸리겠지만 가장 확실한 방법이죠.

    현실은 물론 자기가 한번 한 실수만 안할 수 있어도 대성공입니다만


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.