글 읽기 - 12851번 질문 있습니다.

opop20207 5년 전 0

BFS로 풀었고

테스트케이스는 전부 맞다고 나옵니다.

코드는 visit에 온 횟수를 전부 겹쳐서 계산해주었습니다.

BFS코드진행은 다음과 같습니다.

visit이 0인경우

visit배열엔 현재 위치에서의 visit을 전부 더해줍니다.

visitmax배열에 현재 count를 저장해줍니다.

visit이 0이 아닌경우

visitmax와 현재 count를 비교해서

현재 count가 같거나 낮을경우 visit배열에 현재 위치에서의 visit을 전부 더해줍니다.

visit[N]=1로 설정해줍니다.

간단한거같은데 안풀립니다. 도와주십시오.

#include <stdio.h>

int visit[1000000] = { 0 };
int visitmax[1000000] = { 0 };
int input = 0, output = 0;
int N, K;
int ret = -1;

typedef struct XC {
	int X;
	int Count;
}XC;

XC A[1000000];

void EnQ(XC data)
{
	A[input] = data;
	input++;
}
XC DeQ()
{
	XC temp = A[output];
	output++;
	return temp;
}

int BFS()
{
	XC Temp;
	Temp.X = N;
	Temp.Count = 0;
	EnQ(Temp);
	visit[N] = 1;

	while (input != output)
	{
		XC current = DeQ();

		

		if (current.X == K && ret == -1) {
			ret = current.Count;
		}
			
		if (ret < current.Count && ret != -1) {
			return ret;
		}

		if (current.X * 2 <= 100000)
		{
			if (visit[current.X * 2] == 0) {
				Temp.X = current.X * 2;
				Temp.Count = current.Count + 1;
				visit[current.X * 2] += visit[current.X];
				visitmax[current.X * 2] = current.Count;
				EnQ(Temp);
			}
			else if (current.Count <= visitmax[current.X * 2]) {
				visit[current.X * 2] += visit[current.X];
			}
		}
		if (current.X - 1 >= 0)
		{
			if (visit[current.X - 1] == 0) {
				Temp.X = current.X - 1;
				Temp.Count = current.Count + 1;
				visit[current.X - 1] += visit[current.X];
				visitmax[current.X - 1] = current.Count;
				EnQ(Temp);
			}
			else if (current.Count <= visitmax[current.X - 1]) {
				visit[current.X - 1] += visit[current.X];
			}
		}
		if (current.X + 1 <= 100000)
		{
			if (visit[current.X + 1] == 0) {
				Temp.X = current.X + 1;
				Temp.Count = current.Count + 1;
				visit[current.X + 1] += visit[current.X];
				visitmax[current.X + 1] = current.Count;
				EnQ(Temp);
			}
			else if (current.Count <= visitmax[current.X + 1]) {
				visit[current.X + 1] += visit[current.X];
			}
		}
	}
}
int main()
{
	scanf("%d %d", &N, &K);
	if (N >= K) {
		printf("%d\n1\n", N - K);
		return 0;
	}
	printf("%d\n", BFS());
	printf("%d\n", visit[K]);
}

seico75 5년 전 1

94줄은 어떤 의미죠?

2 1 이라면 답은 1 2 가 나와야할 것 같고

4 1 이라면 2 2이 나와야 할 것 같은데

저 코드는 아니어 보이네요

opop20207 5년 전 0

N이 K보다 크거나 같은경우 N에서 K로 접근 가능한 방법은 +1이동, -1이동, *2이동중 -1 이동 한가지밖에 없으며, -1이동은 N-K만큼 이루어지므로

N>=K인 경우에

(N,K)의 답은 (N-K,1)이 답이 아닌가요?

2,1일때 2 -> 1(-1)

답 1, 1

4,1일때 4 -> 3(-1) -> 2(-1) -> 1(-1)

답 3, 1

이거 말고 다른 이동방법이 있나요?

seico75 5년 전 2

죄송합니다. 방향은 제가 꺼꾸고 봤네요. 이미 답을 맞추셔서 필요없겠지만

0 1 이 문제였네요.

opop20207 5년 전 0

아니요 ㅠㅠ 봐주셔서 감사합니다. 오류 찾느라고 계속 해맸네요... 간단한거였는데...

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

문제

문제

출처

ICPC

12851번 질문 있습니다.

opop20207 5년 전 0

seico75 5년 전 1

opop20207 5년 전 0

seico75 5년 전 2

opop20207 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말