글 읽기 - 반례를 못찾겠습니다! 도와주세요

9574m 6년 전 0

그래프적 해법이 생각이 안나서 상향 DP를 이용해서 코드를 짰습니다.

배열을 200000개 잡은 것은 20만 번째에는 어떤 좌표가 들어가도 최소에 해낼 수 없기 때문입니당.

문제가 뭘까요?

#include <iostream>
#include <cstdio>

using namespace std;

int dot[200005];

int main()
{
    int N,K;
    int i;

    scanf("%d %d",&N,&K);

    for(i=0;i<N;i++){
        dot[i] = N-i;
    }
    for(i=N+1;i<200005;i++){
        dot[i] = 987654321;
    }

    for(i=N/2;i<200000;i++){
        if(i*2<200000){
            if(dot[i]+1<dot[i*2]){
                dot[i*2] = dot[i] + 1;
            }
        }
        if(dot[i]+1<dot[i-1]) dot[i-1] = dot[i]+1;
        if(dot[i]+1<dot[i+1]) dot[i+1] = dot[i]+1;
    }


    printf("%d",dot[K]);
    return 0;
}

chogahui05 6년 전 0

이 경우에 반례 케이스가 나오네요.

2374 28347

dp식을 어떻게 만드셨나요?

chogahui05 6년 전 1

그래프적 해법은 어렵게 생각하실 필요가 없어요.

3번 지점하고 연결이 되어 있는 것은 2, 4, 6이잖아요. 단방향으로

그러면 연결 시키면 됩니다.

[3][2] = connect. [3][4] = connect. [3][6] = connect.

다만, 노드의 수가 10만개이므로, 인접 배열로 관리하는 건 힘들고요. 인접 리스트로 관리를 하는 게 좋겠지요.

보통 vector로 많이 코딩하십니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다! 도와주세요

9574m 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말