글 읽기 - 숨바꼭질 질문입니다~ 알려주시면 고맙겠습니다~

tddhot2 6년 전 0

- 방문하는 지점에서 dp로 저장해 두번 같은 경로를 방문하지 않도록 했습니다.

- 문제가 테스트케이스를 1 100000이렇게 두면 프로그램이 죽어버리더군요.. 아무래도 재귀호출을 많이 해서 그런것 같기도 한데 잘 모르겠습니다

- 주어진 TC에 대해서는 정답입니다. 시간내주셔서 알려주시면 많은 도움이 될 것 같습니다~ +_+

#include <iostream>
using namespace std;

int N, K;
int dp[100001];

int Solution(int now) {

	if (now == K) 
		return 0;

	if (dp[now] != 99999)
		return dp[now];

	int a, b, c;

	if (now < K && now * 2 <= 100000) {
		c = 1 + Solution(now * 2);
		if (dp[now] > c)
			dp[now] = c;
	}


	if (now - 1 >= 0 && now * 2 > K) {
		b = 1 + Solution(now - 1);
		if (dp[now] > b)
			dp[now] = b;
	}


	if (now + 1 <= K) {
		a = 1 + Solution(now + 1);
		if (dp[now] > a)
			dp[now] = a;
	}

	return dp[now];
}

int main() {

	cin >> N >> K;
	for (int i = 0; i <= 100000; i++)
		dp[i] = 99999;
	cout << Solution(N) << endl;

	return 0;
}

zxcv1534 6년 전 1

숫자가 커서 스택 오버플로우가 난다는 얘기시죠??

이 문제는 재귀호출로 풀기엔 무리입니다. 백트래킹 기법을 한 번 알아보세요.

tddhot2 6년 전 0

아 이문제가 아예 재귀호출로는 안되는 문제인가요??

저는 쟤가 어느 부분을 잘 못해서 그렇게 되는 줄 알아서요

zxcv1534 6년 전 1

재귀호출로 안 되는 이유는 답에 도착하기 전에 스택의 허용량을 벗어나기 떄문입니다. 어느 부분을 잘 못 하신 건 아닙니다. 아마 숫자가 적당하다면 답이 충분히 나올 수 있습니다. 한 번 재귀호출이 아닌 한 번에 구할 방법을 생각해보세요. 예를 들자면 만약 도착점이 왼쪽에 있다면 3가지 방향 중 가능한 것은 왼쪽 하나밖에 없겠죠?

그럼 계속 1+f(x-1)을 하지 말고 한 번에 도착점과의 왼쪽 거리만큼을 반환하면 됩니다.

여기서 백트래킹 사용을 권장하는 이유는 위와 같이 한 번에 구할 수 있게끔 가지치기를 많이 할 수 있기 때문입니다.

zxcv1534 6년 전 1

참고로 스택 허용량이 문제라면 큐를 직접 생성하여 BFS 방식으로 풀수도 있습니다. 자동으로 생성되는 스택 허용량보다 동적배열이 더 많은 허용량을 갖거든요.

tddhot2 6년 전 1

zxcv1534 친절한 설명 너무나 감사드립니다~ 말씀하신대로 적은 범위의 TC에서는 올바른 정답을 내지만 끝에서 끝으로 진행하면 스택호출로 하다보니 안되는 게 맞는 것 같습니다~ BFS방식으로 해결하였습니다 감사합니다!

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

문제

문제

출처

ICPC

숨바꼭질 질문입니다~ 알려주시면 고맙겠습니다~

tddhot2 6년 전 0

zxcv1534 6년 전 1

tddhot2 6년 전 0

zxcv1534 6년 전 1

zxcv1534 6년 전 1

tddhot2 6년 전 1

zxcv1534 친절한 설명 너무나 감사드립니다~ 말씀하신대로 적은 범위의 TC에서는 올바른 정답을 내지만 끝에서 끝으로 진행하면 스택호출로 하다보니 안되는 게 맞는 것 같습니다~ BFS방식으로 해결하였습니다 감사합니다!

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말