글 읽기 - 왜 BFS가 아니라 DP & 왜 메모리 초과인가요

vegatrash 5년 전 0

vector을 백만개공간을 할당해도 겨우 4메가바이트 밖에 안되는데 어디서 나머지 120메가가 채워진건지 감이 오지 않습니다..

그리고 문제 처음 봤을 때 DP인걸 보고 들어오긴 했지만 그걸 안보고 들어왔다고 가정하고 생각해보니

첫인상이 딱 얘는 BFS로 푸는거겠구나 싶어서 일단 그렇게 풀었는데

콘솔창에서 10만을 입력하면 2초정도만에 답이 나와서 시간이 초과가 되더군요... 그리고 제출해보니 메모리 초과라고 뜹니다..

이런 문제를 봤을 때 어떻게 DP문제라는걸 바로 캐치해야하나요?

그리고 왜 메모리가 초과가 나나요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <time.h>
#include <memory.h>
#include <functional>

using namespace std;

typedef long long ll;

queue<int> q;
vector<int> v(1000001);

int BFS(int n) {
	int pointer = 0;
	q.push(1);
	v[pointer]++;
	while (true) {
		int now = q.front();
		q.pop();
		v[pointer]--;

		if (now == n) return pointer;
		if (now * 3 <= n) {
			q.push(now * 3);
			v[pointer + 1]++;
		}
		if (now * 2 <= n) {
			q.push(now * 2);
			v[pointer + 1]++;
		}
		if (now + 1 <= n) {
			q.push(now + 1);
			v[pointer + 1]++;
		}
		if (v[pointer] == 0) {
			pointer++;
		}
	}
	return pointer;
}

int main() {
	int n, cnt = 0;
	cin >> n;
	cout << BFS(n);

	return  0;
}

njw1204 5년 전 0

BFS가 안 되는 이유가 뭘까요? 시간복잡도와 공간복잡도 모두 괜찮을것 같은데..

사실 코드에 잘못된 점이 있습니다.

njw1204 5년 전 0

그리고 메모리 초과가 날만한 이유는 큐에 너무 많은 원소를 집어넣는 것밖에 보이지 않네요

jwvg0425 5년 전 0

njw님 말씀대로 코드에 잘못된 점이 있고 이 문제는 bfs로도 충분히 풀 수 있는 문제입니다. 문제 분류에 너무 연연하지 마세요

vegatrash 5년 전 0

아무리 들여다 봐도 잘못된점이 잘 안보이는데...

굳이 찾겠다면 큐에 들어갈 원소들이 중복될 수 있다는점.

하지만 이것때문에 층 수 계산이 잘못되지도 않는데 어디가 잘못된건가요?

실제로 3^16을 적으면 16이라고 답이 잘 나옵니다 ㅠ

vegatrash 5년 전 0

체크 배열을 만들어서 중복된게 있는지 검사해서 제출하니 통과되네요 -_-;

큐에서 메모리가 120메가나 나왔나봅니다...

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

문제

문제

출처

ICPC

왜 BFS가 아니라 DP & 왜 메모리 초과인가요

vegatrash 5년 전 0

njw1204 5년 전 0

njw1204 5년 전 0

jwvg0425 5년 전 0

vegatrash 5년 전 0

vegatrash 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말