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

nablyy 6년 전 0

진행되다가 틀리는데 도대체 어디서 틀린걸까요ㅠㅠ

반례를 찾아주시면 감사하겠습니당...도와주세요!!!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/1697

public class Main {
	
	private static final int n = 100000;
	private static int max = 0;
	private static int min = 0;
	private static int t = 0;
	
	private static int bfs(ArrayList<Integer>[] aGraph, boolean[] check) {
		Queue<Integer> q = new LinkedList<Integer>();
		ArrayList<Integer> result = new ArrayList<Integer>();
		int count[] = new int[n+1];
		Arrays.fill(count, 0);
		
		Arrays.fill(check, false);
		q.add(min);
		check[min] = true;
		
		while(true) {
			int x = q.poll();
			result.add(x);
			if(x == max) {
				t = x;
				break;
			}
			for(int y: aGraph[x]) {
				if(!check[y]) {
					q.add(y);
					check[y] = true;
					count[y] = count[x]+1;
				}
			}
		}
		
		return count[t];
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		int older = Integer.parseInt(st.nextToken());
		int younger = Integer.parseInt(st.nextToken());
		max = Math.max(older, younger);
		min = Math.min(older, younger);
		
		ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n+1];
		for(int i=0; i<=n; i++) {
			graph[i] = new ArrayList<Integer>();
			if(i+1<=n) {
				graph[i].add(i+1);
			}
			if(i-1>=0) {
				graph[i].add(i-1);
			}
			if(i*2<=n) {
				graph[i].add(i*2);
			}
		}
		for(int i=0; i<n; i++) {
			Collections.sort(graph[i]);
		}
		
		boolean[] check = new boolean[n+1];
		System.out.println(bfs(graph, check));
	}

}

kesakiyo 6년 전 0

큐의 크기와 그래프를 만들 때 범위를 조금 더 크게 잡아보세요.

100000보다 커진다음에 1씩 감소하는게 이득일수도 있어요.

nablyy 6년 전 0

해결됬어요

max = Math.max(older, younger);

min = Math.min(older, younger);

이게 문제였어요ㅜ!!

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

문제

문제

출처

ICPC

반례좀 찾아주세요ㅠㅠ

nablyy 6년 전 0

kesakiyo 6년 전 0

nablyy 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말