글 읽기 - bfs- 맞았습니다. / dp

wjddydgns99 4년 전 0

이유를 모르겠습니다...

저거 역추적 숨바꼭질 2인가 4인가에서 비슷하게 bfs로 풀었던 거라 bfs로는 쉽게 해결했는데요.

dp로 하려니깐 잘 안됩니다...

dp를 어떻게 수정해야 올바르게 나올까요...?

문제의 예시는 잘 나옵니다.

//dp-틀렸습니다.
#include<iostream>

using namespace std;

int arr[1000001];
int from[1000001];
void print(int x)
{
	if (from[x] == 0)
	{
		cout << x << " ";
		return;
	}
	print(from[x]);
	cout << x << " ";
}
int go(int x)
{
	if (x <= 1) return 0;
	if (arr[x] > 0) return arr[x];
	arr[x] = go(x - 1) + 1;
	from[x - 1] = x;
	if (x % 2 == 0)
	{
		int k = go(x / 2) + 1;
		if (arr[x] > k) {
			arr[x] = k;
			from[x / 2] = x;
		}
	}
	if (x % 3 == 0)
	{
		int k = go(x / 3) + 1;
		if (arr[x] > k) {
			from[x / 3] = x;
			arr[x] = k;
		}
	}
	return arr[x];
}

int main()
{
	int x; cin >> x;
	cout << go(x) << "\n";
	print(1);
}


//bfs -  맞았습니다.

#include<iostream>
#include<queue>

using namespace std;

bool check[1000001];
int answer[1000001];
int from[1000001];
void print(int x)
{
	if (from[x] == 0)
	{
		cout << x << " "; return;
	}
	print(from[x]);
	cout << x << " ";
}
int main()
{
	int x; cin >> x;
	queue<int> q;
	q.push(x);
	check[x] = true;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		if (x < 1 || x>1000000) continue;
		if (x % 3 == 0)
		{
			if (check[x/3] == false)
			{
				q.push(x/3);
				check[x/3] = true;
				answer[x / 3] = answer[x] + 1;
				from[x/3] = x;
			}
			else if (answer[x / 3] > answer[x] + 1)
			{
				answer[x / 3] = answer[x] + 1;
				from[x/3] = x;
			}
		}
		if (x % 2 == 0)
		{
			if (check[x / 2] == false)
			{
				q.push(x / 2);
				check[x / 2] = true;
				answer[x / 2] = answer[x] + 1;
				from[x/2] = x;
			}
			else if (answer[x / 2] > answer[x] + 1)
			{
				answer[x / 2] = answer[x] + 1;
				from[x/2] = x;
			}
		}
		if (check[x - 1] == false)
		{
			q.push(x - 1);
			check[x - 1] = true;
			answer[x - 1] = answer[x] + 1;
			from[x-1] = x ;
		}
		else if (answer[x - 1] > answer[x] + 1)
		{
			answer[x - 1] = answer[x] + 1;
			from[x-1] = x;
		}
	}
	cout << answer[1] << "\n";
	print(1);
}

easy03 4년 전 0

x가 8일때

위의 코드의 결과

8 7 6 3 1

답

8 4 2 1

arr배열은 값이 잘 나오는데 from배열이 이상합니다. from[1]에 3만 저장되니 값이 이상하게 나옵니다.

작은 숫자에 큰 숫자의 값을 저장해서 출력하는 게 아닌 큰 숫자에 작은 숫자의 값을 저장해서 출력하는 방식으로 하는 게 좋을 것 같습니다.

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

문제

문제

출처

ICPC

bfs- 맞았습니다. / dp - 틀렸습니다.

wjddydgns99 4년 전 0

easy03 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말