글 읽기 - 시간초과 발생원인 및 제 풀이방법이 맞는지 알려주시면 감사하겠습니다.

yookyuhawn 2년 전 0

질문 1. 제 코드에서 시간초과가 발생하는 이유를 모르겠습니다.

질문 2. 시간초과를 제외하고, 논리적으로 현 코드가 문제해결이 가능한지 궁금합니다. (저의 알고리즘이 타당한지)

질문에 대한 답변 감사합니다!!

#include<stdio.h>

int min;
int cache[100001];
int dis;

int solve(int N, int K, int move){
	if(N<0 || N>100000) return 9999999;
	if(N > K+dis ) return 9999999; //N이 K+dis보다 커지게 되면 이동횟수(move) >= dis + 1;  하지만, 처음부터 +1만 해도 move = dis 이므로 
	if(N == K){
		if(move < min){ 
			min = move;
			return min;
		}else {return 9999999;}
	}
	if(min < move) return 9999999; 
	
	

	if(cache[N]){
		if(move < cache[N]){
			cache[N] = move;
		}else{
			return 9999999; //중복 방문 제외
		}
	}else{
		cache[N] = move;
	}
	
	int r = solve(N+1, K, move+1);
	int r2=solve(N-1, K, move+1);
	int r3=solve(N*2, K, move+1);
	if(r > r2) r= r2;
	if(r > r3) r= r3;
	
	return r;
}

int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	min = 9999999;
	dis = K-N;
	if(dis < 0) dis = dis*(-1);  
	int result = solve(N, K, 0);
	printf("%d", result);
	
	
	return 0;
}

kdw8573 2년 전 1

저의 짧은 지식으로 코드를 보면 DFS로 짜신거 같습니다. DFS로 구현할 경우 목적지에 최소 움직임으로 도달하게 될 때까지 너무 많은 재귀를 돌게 되서 시간초과가 나지 않았을까

짐작해봅니다.

BFS로 구현한다면 목적지에 도달했을 때가 바로 최소 움직임을 보장할 수 있으니 BFS로 구현하면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

시간초과 발생원인 및 제 풀이방법이 맞는지 알려주시면 감사하겠습니다.

yookyuhawn 2년 전 0

kdw8573 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말