글 읽기 - 왜 틀렸을까요

dth04019 7년 전 0

큐로 구현했고 중복된 수가 안나오케 체크하되 도착점은 체크하지 않아서 같은 시간에 도착할 수 있는 경우의 수를 세렸는데 왜 틀렸을까요 ㅜㅜ

#include <stdio.h>
int xx[5000000], xt[5000000], st, ed, N, K, chk[110000];

void inque(int a, int b){
	xx[st] = a, xt[st] = b;
	++st;
}
int main(void)

{
	int i, j, k, vl = 0, time = 0;

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

	inque(N, 0);

	while (st != ed){
		if (xx[ed] == K){
			k = ed;
			while (xt[k] == xt[ed]){
				if (xx[k] == K){
					++vl;
				}
				++k;
			}
			break;
		}
		if (chk[xx[ed] + 1] == 0 && xx[ed] + 1 <= 100002){
			inque(xx[ed] + 1, xt[ed] + 1);
			if (xx[ed] + 1 == K){}
			else{
				chk[xx[ed] + 1] = 1;
			}
		}	
		if (chk[xx[ed] - 1] == 0 && xx[ed] -1 >= 0){
			inque(xx[ed] - 1, xt[ed] + 1);
			if (xx[ed] - 1 == K){}
			else{
				chk[xx[ed] - 1] = 1;
			}
		}
		if (chk[xx[ed] * 2] == 0 && xx[ed] * 2 <= 100002){
			inque(xx[ed] * 2, xt[ed] + 1);
			if (xx[ed] *2 == K){}
			else{
				chk[xx[ed] *2] = 1;
			}
		}
		++ed, time;
	}

	printf("%d\n", xt[ed]);
	printf("%d", vl);

	return 0;
}

gkourr1541 7년 전 1

도착지점만 체크를 안하는걸로는 오답이 나옵니다.

예를들어 input이 1 10 이라 하면

output은 4 2 가 나와야하는데

4 1 이 나오네요.

경로는

1 -> 2(+1) -> 4(*2)->5(+1)->10(*2)

1 -> 2(*2) -> 4(*2)->5(+1)->10(*2)

이렇게 두개인데 2부분에서 하나는 두배로 온거고 하나는 +1로 온거로 두개가 다른거지만

chk에 걸려서 하나는 걸러지고 하나만 큐에 들어가기때문에 4 1로 나오는것 같습니다

dth04019 7년 전 0

오 그렇군여 생각이 짧았네여 ㅜㅜ 감사합니다!

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

문제

문제

출처

ICPC

왜 틀렸을까요

dth04019 7년 전 0

gkourr1541 7년 전 1

dth04019 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말