글 읽기 - 1697번 틀렸습니다가 뜨는데 반례를 못 찾겠습니다..

qkrtjdqls031 5년 전 0

맞을 것이라고 확신했는데 틀렸습니다가 떠서 당황했는데

몇몇의 제가 생각한 예제를 넣어봐도 잘 돌아가서 어떤 반례가 있는지 잘 모르겠씁니다..

의견 주시면 감사하겠습니다.

이해가 안 가는 점 있으시면 질문해 주셔도 됩니다.

#include <stdio.h>

typedef struct findk
{
	int number;//숫자 저장
	int times;//이동 횟수 저장
}findk;

findk queue[100001];
int check[100001]={0};
/*
check 배열은 1~100000까지 숫자 중 중복이 발생할 수 있으므로 이를 방지하기 위함
즉, 3->6->5, 3->4->5면 5가 중복으로 발생하므로, 이를 방지하기 위해서
숫자가 나올 때 마다 배열의 값을 1로 설정한다. 0일 경우에만 중복이 아님.
*/
int main()
{
	int n, k;
	scanf("%d %d",&n,&k);
	int start=0, end=0;//end는 queue에 다음에 넣어야 할 위치

	queue[start].times=0;//처음 위치는 0회 이동
	queue[end++].number=n;//처음 위치 저장
	check[n]=1;
	while(queue[start].number!=k)//목표인 k에 도달할 때 까지 반복
	{
		
		//N-1
		if(queue[start].number-1>0)//0이하는 의미 없으므로 제외
		{
			if(check[queue[start].number-1]==0)//아직 안 나온 숫자라면
			{
				//queue에 저장 및 check 초기화
				check[queue[start].number-1]=1;
				queue[end].number=queue[start].number-1;
				queue[end++].times=queue[start].times+1;
			}
		}
		//N+1
		if(queue[start].number+1<=100000)//100000초과는 의미 없으므로 제외
		{
			if(check[queue[start].number+1]==0)//아직 안 나온 숫자라면
			{
				//queue에 저장 및 check 초기화
				check[queue[start].number+1]=1;
				queue[end].number=queue[start].number+1;
				queue[end++].times=queue[start].times+1;
			}
		}

		//2N
		if(2*queue[start].number<=100000)//100000초과는 의미 없으므로 제외
		{
			if(check[2*queue[start].number]==0)//아직 안 나온 숫자라면
			{
				//queue에 저장 및 check 초기화
				check[2*queue[start].number]=1;
				queue[end].number=2*queue[start].number;
				queue[end++].times=queue[start].times+1;
			}
		}
		start++;//queue의 다음 항으로
	}

	printf("%d",queue[start].times);//최종 나온 숫자가 몇 번만에 도달했는지.
	return 0;
}

hello70825 5년 전 1

좌표의 범위가 0~100000 입니다.

29줄에 >= 로 바꾸면 돌아갈 것 같습니다.

qkrtjdqls031 5년 전 1

답변주셔서 감사합니다..!!!! 출발하는 사람이 0인 것만 생각했었는데 도착점이 0일 수도 있음을 생각을 못했군요..

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

문제

문제

출처

ICPC

1697번 틀렸습니다가 뜨는데 반례를 못 찾겠습니다..

qkrtjdqls031 5년 전 0

hello70825 5년 전 1

qkrtjdqls031 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말