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

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;

	if (n == k) {
		cout << 0 << endl;
		return 0;
	}

	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년 전 0

아까 질문에서 https://www.acmicpc.net/board/... 를 한 번 읽어보셨으면 좋겠다고 말씀드렸는데, 읽어보셨나요?

djm03178 4년 전 0

참고로 반례도 아까 드렸던 것과 같습니다. 0만 출력하고 끝내면 안 됩니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다!

skesswswkk 4년 전 0

djm03178 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말