글 읽기 - 살려주세오 모르겠어요

syl0390 1년 전 1

반례

5 1000

답: 11 2

5 100000

답 : 19 5

라는데 제가 봤을 때는 코드 상에 어떤 문제가 있는지 모르겠고...

두개 출력은 11 1, 19 1 나오고...

도와주시면 감사하겠습니다..

#include <iostream>
#include <queue>

using namespace std;

int N, K, cnt = 1;
int ans[100001] = {0, };

void bfs(int start, int end){
    ans[start] = 0;
    queue<int> q;
    q.push(start);
    int found = 0;

    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        

        int dx[] = {x - 1, x + 1, x * 2};

        for(int i =0; i< 3; i++){
            if(0 <= dx[i] && dx[i] <= 100000){
                if(ans[dx[i]] == 0){
                    ans[dx[i]] = ans[x] + 1;

                    if(dx[i] == end) found++;
                    if(found != 0) continue;
                    
                    q.push(dx[i]);
                } else if(dx[i] == end && ans[x] + 1 == ans[end]) cnt++;
            }

        }
    }
    
}

int main(){
    scanf("%d %d", &N, &K);
    bfs(N, K);

    cout << ans[K] << '\n' << cnt;

    return 0;
}

osthus 1년 전 0

도착점이 아닌 점에서 최단 시간으로 같은 점을 여러 번 방문하였을 때 방법을 세는 부분이 없습니다. 예를 들어 N = 1, K = 3 케이스에는 아래와 같이 2개의 경우가 존재합니다.

1. 1 (+1) -> 2 (+1) -> 3

2. 1 (*2) -> 2 (+1) -> 3

kku64r 1년 전 4

다른 분들이 헷갈리실까봐 남겨요.

5 100000 답은 19 4입니다. 이 부분 틀린 줄 알고 찾다가 헤맸네요..

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

문제

문제

출처

ICPC

살려주세오 모르겠어요

syl0390 1년 전 1

osthus 1년 전 0

kku64r 1년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말