글 읽기 - 반례 부탁드립니다

skesswswkk 4년 전 0

문제의 입출력과 질문의 반례는 다 맞다고 나옵니다! 반례 몇 가지만 부탁드립니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int M = 100000 + 1;

int parent[M];
int visited[M];
vector<int> v;

int main() {
	int n, k;
	cin >> n >> k;

	queue<pair<int, int>> q;
	q.push({n, 0});

	while (!q.empty()) {
		int num = q.front().first;
		int cnt = q.front().second;
		q.pop();

		//종료조건
		if (num == k) {
			cout << cnt << endl;

			v.push_back(num);//17
			while (parent[num] != n) {//18 //9 //10 //
				v.push_back(parent[num]);//18 //9 //10
				num = parent[num];//18 //9 //10
			}

			cout << n << " ";
			for (int i = v.size() - 1; i >= 0; --i) {
				cout << v[i] << " ";
			}
			return 0;
		}

		//01
		int tmp = num - 1;
		if (tmp >= 0 && !visited[tmp]) {
			visited[tmp] = 1;
			q.push({ tmp, cnt + 1 });
			parent[tmp] = num;
		}

		//02
		tmp = num + 1;
		if (tmp < M && !visited[tmp]) {
			visited[tmp] = 1;
			q.push({ tmp, cnt + 1 });
			parent[tmp] = num;
		}
		
		//03
		tmp = num * 2;
		if (tmp < M && !visited[tmp]) {
			visited[tmp] = 1;
			q.push({ tmp, cnt + 1 });
			parent[tmp] = num;
		}
	}
}

djm03178 4년 전 1

질문을 할 때는 제출했던 코드를 한 글자도 다름없이 그대로 올려주셔야 합니다. 메모리 초과를 받으신 적이 없는데, 이 코드를 그대로 내면 메모리 초과가 납니다.

skesswswkk 4년 전 0

중간에 수정했던 코드를 올렸네요 죄송합니다. 아래 소스 코드는 틀렸습니다가 나오는 코드 입니다! 반례 부탁드립니다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int M = 100000;

int parent[M];
int visited[M];
vector<int> v;
int main() {
	int n, k;
	cin >> n >> k;

	queue<pair<int, int>> q;
	q.push({ n, 0 });

	while (!q.empty()) {
		int num = q.front().first;
		int cnt = q.front().second;
		q.pop();

		//종료조건
		if (num == k) {
			cout << cnt << endl;

			v.push_back(num);//17
			while (parent[num] != n) {//18 //9 //10 //
				v.push_back(parent[num]);//18 //9 //10
				num = parent[num];//18 //9 //10
			}

			cout << n << " ";
			for (int i = v.size() - 1; i >= 0; --i) {
				cout << v[i] << " ";
			}
			return 0;
		}

		//01
		int tmp = num - 1;
		if (tmp >= 0 && !visited[tmp]) {
			visited[tmp] = 1;
			q.push({ tmp, cnt + 1 });
			parent[tmp] = num;
		}

		//02
		tmp = num + 1;
		if (tmp <= 100000 && !visited[tmp]) {
			visited[tmp] = 1;
			q.push({ tmp, cnt + 1 });
			parent[tmp] = num;
		}

		//03
		tmp = num * 2;
		if (tmp <= 100000 && !visited[tmp]) {
			visited[tmp] = 1;
			q.push({ tmp, cnt + 1 });
			parent[tmp] = num;
		}
	}
}

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

문제

문제

출처

ICPC

반례 부탁드립니다

skesswswkk 4년 전 0

djm03178 4년 전 1

skesswswkk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말