글 읽기 - 반례 모르겠습니다 자꾸틀렸다고 뜨네요...

shin748 5년 전 0

4부터 최소횟수를 찾아서 n까지 도달하는 방법입니다.

2로 나누는 경우 : n/2가 될테니 count에 +1합니다. 이후 dp의 n/2번째 index(즉 dp[n/2]) 속의 최소횟수를 더해주면 됩니다.

그래서 count=1+dp[i/2] 가 최소라고 하고 prov[0]에 넣습니다

3으로 나눌때는 prov[1]에, 1뺄때 prov[2]에 넣습니다.

이후 prov배열에서 진짜 최솟값을 찾아주는 식으로 했습니다.

질문게시판에 나온 대입값 모두 해봤는데 모두 잘 나와서 뭐가 틀렸단건지 문제점을 모르겠습니다..

#include <stdio.h>

 
int main()

{
    int dp[1000002]={0,0,1,1};
    int prov[3]={0}; //prov[0]은 2를나눈값, [1]은 3을, [2]는 1뺀 값을 넣고, 셋을 비교할생각
    int n, count=0;
    int num, least, li;
    
    scanf("%d",&n);
    if(n<4){ //0~3 처리
        for(int i=0;i<4;i++){
            if(i==n){
                printf("%d\n",dp[i]);
                return 0;
            }
        }
    }
    
    for(int i=4;i<=n;i++) //4부터 돌려서 n까지 쌓으며 답 낼 계획
    {
        if(i%2==0){ //2로 나눌수 있다면?
            num=i/2; 
            count+=1;
             count+=dp[num]; //i를 2로 나눈 값과 같은 index속에 이미 그 값의 최소횟수가 있음을 이용
            prov[0]=count; 
        }
        
        if(i%3==0){ //3이면? 
            num=i/3;
            count+=1;
            count+=dp[num]; //마찬가지
            prov[1]=count;
        }
        
        //1빼기를 강제적으로 하기
            num=i-1; //1빼기
            count=1; //강제 초기화
            count+=dp[num]; //걔가 가진 횟수만큼 더하고 나간다.
            prov[2]=count;
                
        least=prov[0];
        if(least!=0 && prov[1]!=0){ //if에 안들어가면 prov배열중 0이 존재할테니, 비교시 0을 최소로 잡는 일이 벌어짐. 그걸 막기위한 if문들
            least=prov[0];
            li=0;
        }
        else if(least==0 && prov[1]!=0){ 
            least=prov[1];
            li=1;
        }
        else if(least==0 && prov[1]==0){ 
            least=prov[2];
            li=2;
        }
        else if(least!=0 && prov[1]==0){ 
            least=prov[0];
            li=0;
        }

        for(int j=li+1;j<3;j++){ //크기 비교시작
            if(prov[j]==0)
                continue;
            if(least>=prov[j])
                least=prov[j];
        }
        dp[i]=least; //이 모든과정을 거친 값이 정확한 최소니까 마침내 대입
        count=0; //초기화1
        for(int j=0;j<3;j++) //초기화2
            prov[j]=0;
    } 
    printf("%d\n",dp[n]); //결국 구할값까지 채워졌을테니 구할값 출력
}

trimind 5년 전 0

Input : 30

output : 5

expected output : 4

30의 경우 `30 -> 10 -> 9 -> 3 -> 1` 4번으로 가능합니다.

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

문제

문제

출처

ICPC

반례 모르겠습니다 자꾸틀렸다고 뜨네요...

shin748 5년 전 0

trimind 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말