글 읽기 - 1697 메모제이션 dp로 풀고있는데 어디서 틀렸는지 모르겠어요

qkrtk27 3년 전 0

질문 게시판에 있는 반례들을 찾아보기도 해봤는데 해결이 안됩니다.

bfs말고 dp로 풀어보려고 하고있는데 어디서 틀렸는지 계속 모르겠습니다 ㅜㅜ

결과는 틀렸습니다 로 나옵니다. ㅜㅜ

#include <iostream>
#include <cstring>

using namespace std;

int n, k, cache[100001];

//here까지 이동했을 때 시간
int move(int here){
	if(here > 100001 || here < 0){
		return 100002;
	}
	//기저 사례
	if(here == n){
		return 0;
	}
	int& ret = cache[here];
	if(ret != -1){
		return ret;
	}
	
	ret = move(here-1) + 1;
	ret = min(ret, move(here+1) + 1);
	if(here % 2== 0){
		ret = min(ret, move(here/2) +1 );
	}
	return ret;
	
}

int main(int argc, char* argv[]) {
	cin >> n >> k;
	memset(cache, -1, sizeof(cache));
	
	cout << move(k);
	
}

3587jjh 3년 전 1

이 문제는 here들간에 사이클이 존재하기 때문에 이를 따로 해결해주지 않는 한 dp로 해결할 수 없습니다

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

문제

문제

출처

ICPC

1697 메모제이션 dp로 풀고있는데 어디서 틀렸는지 모르겠어요

qkrtk27 3년 전 0

3587jjh 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말