글 읽기 - 어떻게 접근해야 할 지 모르겠습니다.

wjddms206 6년 전 0

숨바꼭질1 은 visit배열을 써서 bfs로 풀었습니다.

이 문제도 visit 배열로 풀려고 했으나 45%에서 틀렸습니다가 나와 찾아보니

[질문]의 어떤 고수님의 답처럼,

1 -> 2(+1) -> 4(*2)->5(+1)->10(*2)

1 -> 2(*2) -> 4(*2)->5(+1)->10(*2)

이렇게 두개인데 2부분에서 하나는 두배로 온거고 하나는 +1로 온거로 두개가 다른거지만

비짓배열에 걸려서 하나는 걸러지고 하나만 큐에 들어가기때문에 4 1로 나오는 상황이 발생했습니다.

그래서 visit배열을 안쓰고 푸는 방법으로 했지만 7%에서 메모리초과..

어떻게 풀어야 할지 감이 안옵니다. ㅠㅠ 도와주세요..ㅠㅠ

(visit배열 쓰지 않은 7% 메모리 초과 소스코드입니다.)

#include <iostream>
#include <queue>
using namespace std;

int n, k;

int main()
{
	cin >> n >> k;
	queue<pair<int,int>> q;
	q.push(make_pair(0,n));

	int ret_sec = -1;
	int ret_cnt = 1;
	while (!q.empty()) {
		int w = q.front().first;
		int curNode = q.front().second;
		q.pop();

		//cout << ret_sec << "," << w << "," << curNode << endl;

		if (curNode - 1 >= 0 ){
			if (ret_sec != -1 && ret_sec <= w){}
			else if (curNode - 1 == k) {
				if (ret_sec == -1) ret_sec = w+1;
				else ret_cnt++;
			}
			else q.push(make_pair(w + 1, curNode - 1));
		}
		if (curNode + 1 <= 100000) {
			if (ret_sec != -1 && ret_sec <= w) {}
			else if (curNode + 1 == k) {
				if (ret_sec == -1) ret_sec = w+1;
				else ret_cnt++;
			}
			else q.push(make_pair(w + 1, curNode + 1));
		}
		if (curNode * 2 <= 100000 ){
			if (ret_sec != -1 && ret_sec <= w) {}
			else if (curNode * 2 == k) {
				if (ret_sec == -1) ret_sec = w+1;
				else ret_cnt++;
			}
			else q.push(make_pair(w + 1, curNode * 2));
		}
	}
	cout << ret_sec << '\n' << ret_cnt;
	return 0;
}

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

문제

문제

출처

ICPC

어떻게 접근해야 할 지 모르겠습니다.

wjddms206 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말