글 읽기 - 반례를 찾아주세요ㅠ

dkfma3323 2년 전 0

올라가다가 틀렸다고 나오는데

어느부분에서 틀린건지 못찾겠네요ㅠ

반례가 있을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, K;
    static int[] visited = new int[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader bw = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bw.readLine());
        N = Integer.parseInt(st.nextToken()); 
        K = Integer.parseInt(st.nextToken());

        if(N == K)  {
            System.out.println(0);
        } else {
            bfs();
            System.out.println(visited[K]);
        }

    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);
        // visited[N] = 0;

        while( !queue.isEmpty() ) {
            int n = queue.poll();

            if(n==K) break;

            if(n*2<=100000 && visited[n*2]==0) {
                queue.add(n*2);
                visited[n*2] = visited[n] + 1;
            }

            if(n+1<=100000 && visited[n+1]==0) {
                queue.add(n+1);
                visited[n+1] = visited[n] + 1;
            }

            if(n-1>=0 && visited[n-1]==0) {
                queue.add(n-1);
                visited[n-1] = visited[n] + 1;
            }
        }

    }
}

dldyddlwl 2년 전 1

아래에 있습니다.

// 원인 : N에 대한 방문처리가 없음

            bfs();        // N에 대한 방문처리를 하지 않으면, N을 또 다시 방문하게 될 수도 있으므로
                        // visited[N] = 1로 해준 후에,
                    // 답에서 1을 빼서, 해결하실 수 있습니다.
            System.out.println(visited[K]);


// visited[N] = 1;
// bfs();
// System.out.println(visited[K]-1);


// 자 방문처리 때문인 건 알았는데, 대체 반례가 뭡니까!! 라고 생각하실 수 있습니다.
// 자, 반례는 N이 0인 경우입니다.

// 0 * 2 = 0이므로, 2배 구간에 들어갑니다. 그러면 visited[0] = visited[0] + 1 = 0 + 1 = 1이 되어버리죠,
// 그러고나서 다른 처리들이 일어나므로, 답보다 1이 크게 나와버리는 것입니다.

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

문제

문제

출처

ICPC

반례를 찾아주세요ㅠ

dkfma3323 2년 전 0

dldyddlwl 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말