글 읽기 - 1697번 문제 질문입니다.

nothappa 5년 전 0

백트래킹으로 풀고 있는데,

온갖 반례들 다 통과시키다가 2374 28347에서 막혔습니다.

답이 608인거 같은데 610이 나오더라구요.

근데 다른 반례는 어떻게든 해결했는데 이번거는 어디서부터 해야할지 감이 안잡히네요.

코드가 좀 난잡하긴 한데 힌트라도 주신다면 감사하겠습니다..

#include <iostream>
using namespace std;
#define INT_MAX 9999999
int result(int now, int target);
int min(int a, int b);

int prio(int a);
int push[200001] = { 0 };
int main() {
	int a, b;
	a = 0;
	b = 0;
	cin >> a >> b;

	cout << result(a,b)<<endl;
	//for (int i = a/2 ; i <b*2;i++)
	//if(push[i]<650&&push[i]>0)
	//cout<<i<<":"<<push[i]<<endl;

	//system("pause");
	return 0;
}
//반1 : 13165 31654, 2663이 정답 31654/2 = 15827 -> 15827-13165 = 2662
//반2 : 2374 28347, 608이 정답
int result(int now, int target) {
	int answer = INT_MAX;

	if (now == target)
		return 0;
	//if (now<0 || now>target * 2)
	if(now<0||now>100001)
		return answer;

	if (push[now] != 0) {
		return push[now];
	}
	push[now] = answer;
	
	if (now>target)
	return now-target;
	
	//if (prio(target-now) < prio(now*2-target)) {
	//	return answer;
	//}



	
	//int temp = 0;
	//cout << now << ">" << answer << endl;
	answer = min(answer,result(now + 1, target) + 1);
	//if (now == 2374 ) cout << answer << endl;
	answer = min(answer, result(now - 1, target) + 1);
	//if (now == 2374 ) cout << answer << endl;
	if (now<target) answer = min(answer, result(now * 2, target) + 1);
	//if (now == 2374 ) cout << answer << endl;
	


	return push[now] = answer;
}
int min(int a, int b) {
	return a>b ? b : a;
}
int prio(int a) {
	return a>0 ? a : -a;
}

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

문제

문제

출처

ICPC

1697번 문제 질문입니다.

nothappa 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말