글 읽기 - 질문게시판 10번째줄까지 확인했는데 반례가 없습니다 왜 틀린지 이해가 안가네요

kjw13 4년 전 0

뭐가 문제인지 이해가 안가네요 무식하게 접근해서 시간초과 나니까 조건대로 수정했는데 일찌감치 실패 ㅋㅋㅋ 웃음만 나오네요 이것만 잡고있기에 어이가없고 시간낭비만 오지네요 반례들 싹다 돌려봐도 반례를 못찾았네요

#include <iostream>

 
using namespace std;
int arr[1000000001];

int dp(int n,long long cnt)
{
    if(n<=1) return 0;
    if(n%3==0)
    {
        if(arr[n/3]==0||arr[n/3]>cnt+1)
        {
            arr[n/3]=cnt+1;
            dp(n/3,cnt+1);
        }
        if(arr[(n-1)/2]==0||arr[(n-1)/2]>cnt+2)
        {
            arr[(n-1)/2]=cnt+2;
            dp((n-1)/2,cnt+2);
        }
    }
    else if(n%2==0)
    {
        if(arr[n/2]==0||arr[n/2]>cnt+1)
        {
            arr[n/2]=cnt+1;
            dp(n/2,cnt+1);
        }
        if(arr[(n-1)/3]==0||arr[(n-1)/3]>cnt+2)
        {
            arr[(n-1)/3]=cnt+2;
            dp((n-1)/3,cnt+2);
        }
    }
    else
    {
        if(arr[n-1]==0||arr[n-1]>cnt+1)
        {
            arr[n-1]=cnt+1;
            dp(n-1,cnt+1);
        }
    }
    return 0;
}


int main(int argc, char** argv)
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int n;
    cin>>n;
    dp(n,0);
    cout<<arr[1]<<"\n";
    return 0;
}  

lovinix 4년 전 0

int arr[1000000001] 의 크기는 얼마인가요?

evenharder 4년 전 2

반례 찾기 조금 힘들었네요. 밑의 설명을 참고해주시기 바랍니다.

예제 입력
284

예제 출력
10

설명
* 284 - 142 - 141 - 47 - 46 - 45 - 15 -  5 - 4 - 2 - 1
* 284 - 283 - 282 - 94 - 93 - 31 - 30 - 10 - 9 - 3 - 1
위 2개의 방법이 10번으로 가장 짧음을 확인할 수 있습니다.

현재 출력
9

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

문제

문제

출처

ICPC

질문게시판 10번째줄까지 확인했는데 반례가 없습니다 왜 틀린지 이해가 안가네요

kjw13 4년 전 0

lovinix 4년 전 0

evenharder 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말