글 읽기 - 1463번 재귀 방식으로 풀어보려하는데 반례를 못 찾겠습니다...

yu4321 4년 전 0

질문 게시판에서 찾을 수 있는 거의 모든 반례를 넣어봐도 다 맞게 나오는데 계속 오답이라고 나오네요...

어디에서 크게 문제가 있는지 좀 부탁드립니다...

#include <iostream>
#include <vector>
using namespace std;

int INF=123456789;

vector<int> memo(1000001,INF);

int GetShortest(int i, int cnt)
{    
    if(memo[i]!=INF){
        return cnt+memo[i];
    }
    
    if(i<=1){
        memo[i]=0;
        return cnt+0;
    }
    
    if(i<=3){
        memo[i]=1;
        return cnt+1;
    }
    int res1=INF;
    int res2=INF;
    int res3=INF;
    if(i%3==0){
        res1=GetShortest(i/3,cnt+1);
    }
    if(i%2==0){
        res2=GetShortest(i/2,cnt+1);
    }
    
    if((i-1)%3==0 || (i-1)%2==0){ 
        res3=GetShortest(i-1,cnt+1);
    }
    
    if(res1<=res2&&res1<=res3){
        memo[i]=res1-cnt;
        return res1;
    }
    if(res2<=res1&&res2<=res3){
        memo[i]=res2-cnt;
        return res2;
    }
    if(res3<=res1&&res3<=res2){
        memo[i]=res3-cnt;
        return res3;
    }
    
    return INF;
}

int main()
{
    int input=0;
    cin>>input;
    int ans=GetShortest(input,0);
    cout<<ans<<endl;
    return 0;
}

nahwasa 4년 전 1

반례입니다.

572

답 : 10 / 출력 : 11

734

답 : 9 / 출력 : 10

그 외에 740, 842 등이 틀렸습니다.

yu4321 4년 전 0

감사합니다! 테스트 환경에서는 세 종류 연산을 무조건 하도록 했을때 500000 넘는 수 넣으면 메모리 초과 떠가지고 조건 걸어놓은거였는데 막상 여기 채점에선 하게 하더라도 아무 문제 없었네요...

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

문제

문제

출처

ICPC

1463번 재귀 방식으로 풀어보려하는데 반례를 못 찾겠습니다...

yu4321 4년 전 0

nahwasa 4년 전 1

yu4321 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말