글 읽기 - [C++]1011번 메모리초과 질문합니다. (백트래킹)

superr 4년 전 0

안녕하세요

1011번을 풀다가 질문드립니다.

문제에 백트래킹방법을 적용해서 가지치기로 풀어보려고 했는데 잘 안되네요

문제에서 제시된 세가지 테스트케이스에 대해서는 잘 동작하는것 확인했고,

혹시 오버플로문제일까해서 사용한 자료형을 int, long long, long, unsigned int 모두 바꿔봤지만 소용이없었습니다.

인터넷에 존재하는 이 문제의 풀이법이 모두 수열의 규칙을 파악해서 이를 응용해 풀이한것들만 존재했는데,

혹시 백트래킹으로 푸신분이 있다면 조언 부탁드리겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAXIMUM 2147483647
using namespace std;
long Answer = MAXIMUM;
long x, y;
void dfs(long curpos, long count, long howmany_move, long target){
	// 현재 위치, 이동 횟수, 기준 이동 거리, 목적지 (진짜 목적지는 target-1)
	// 백트래킹으로 (dfs + pruning) 풀자.

	// y-1지점에 도달했다면 
	// count+1과 Answer를 비교하고 Answer 갱신
	if (curpos == target - 1){
		if (count + 1 < Answer){
			Answer = count + 1;
			return;
		}
	}
	// 이후 지점으로 간다면
	if (curpos >= target){
		// 이동하는 거리는 항상 1이상이므로 target 이상의 위치일 경우 영원히 target-1 위치에 도달하지 못한다.
		// 따라서 이 경우 종료.
		return;
	}
	long left, mid, right;
	left = howmany_move - 1;
	mid = howmany_move;
	right = howmany_move + 1;
	if (left > 0){
		dfs(curpos + left, count + 1, left, target);
	}
	if (mid > 0){
		dfs(curpos + mid, count + 1, mid, target);
	}
	if (right > 0){
		dfs(curpos + right, count + 1, right, target);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long TC;
	cin >> TC;
	for (int i = 0; i<TC; i++){
		cin >> x >> y;
		dfs(x, 0, 0, y);
		cout << Answer << '\n';
		Answer = MAXIMUM;
	}
	return 0;
}

djm03178 4년 전 2

https://www.acmicpc.net/board/view/26059 여기 있는 예시들을 넣었을 때 얼마나 재귀가 깊어질 수 있을지 생각해 보세요. 설령 메모리를 무한히 제공한다고 하더라도 시간 내에 들어오지 못할 것입니다.

superr 4년 전 0

아아 어제 비몽사몽간에 풀다보니 시간복잡도는 신경도안쓰고 풀이했네요. 바로 이유를 알았습니다. 감사합니다.

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

문제

문제

출처

ICPC

[C++]1011번 메모리초과 질문합니다. (백트래킹)

superr 4년 전 0

djm03178 4년 전 2

superr 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말