글 읽기 - 메모리 초과 오류가 떠요 ㅜ

ekfrhkquf12 4년 전 0

말 그대로 .. 메모리 초과 오류가 뜹니다.

bfs로 풀었는데 어떻게 해결하는게 좋을까요 ??

#include<stdio.h>
#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;

int main() {
	int start, target;
	cin >> start >> target;
	
	int temp = 0;
	if (start <= target) temp = target;
	else temp = start;
	int *c = (int *)calloc(100002, sizeof(int)); 
	
	queue<int> bfs;
	bfs.push(start);
	
	while (!bfs.empty()) {
		int temp = bfs.front();
		bfs.pop();

		if (temp == target) break;
		else { //코너 케이스 잘 살펴주기
			bfs.push(temp - 1);
			bfs.push(temp + 1);
			bfs.push(temp * 2);
			if (temp-1>=0 &&temp-1 <= 100001 && c[temp-1] == 0) c[temp - 1] = c[temp] + 1;
			if (temp+1<= 100001 && c[temp+1] == 0) c[temp + 1] = c[temp] + 1;
			if (temp*2<= 100001 && c[temp*2] == 0) c[temp * 2] = c[temp] + 1;
		}
	}
	cout << c[target];
}

cheshirecoder 4년 전 0

1에서 시작하면 0, 2, 2가 추가되고, 그 다음 깊이에서는 -1, 1, 0, 1, 3, 4, 1, 3, 4가 추가됩니다.

한 깊이 돌 때마다 지수 증가하는데 ( O(3ⁿ) ) 이미 넣은 것이나 이미 갔던 곳은 큐에 넣을 필요 없습니다.

이 체크를 사실 28~30라인의 if문들이 할 수도 있을 텐데, 순서가..

엣지 케이스를 큐에 넣고나서 검사하기에 메모리가 충분하다면 런타임 에러도 납니다.

ekfrhkquf12 4년 전 0

말씀해주신대로, 큐에 넣기 전에 if문을 이용해서 걸러주니 메모리 오류가 나지 않고 정답으로 채점되었습니다.

감사합니다. !!

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

문제

문제

출처

ICPC

메모리 초과 오류가 떠요 ㅜ

ekfrhkquf12 4년 전 0

cheshirecoder 4년 전 0

ekfrhkquf12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말