글 읽기 - 틀린 부분좀 찾아주세요

yih9329 7년 전 0

계속 오류를 고치다가 결국 다 되는 최선의 풀이라고 생각되는 걸로 했는데

결국 틀렸다고 나오네요

어떤 부분에서 오류가 나는 건지 알려주시면 감사하겠습니다

구현방식은 bfs 방식으로 했습니다.

#include<iostream>
using namespace std;

int queue[1000][2];
int head = 0, tail = 0;

int bfs(int n, int cost)
{
	tail %= 1000;
	if (n == 1)
		return queue[head][1];
	
	if (n % 3 == 0)
	{
		queue[tail][0] = n / 3;
		queue[tail++][1] = cost + 1;
	}

	if (n % 2 == 0)
	{
		queue[tail][0] = n / 2;
		queue[tail++][1] = cost + 1;
	}
	queue[tail][0] = n - 1;
	queue[tail++][1] = cost + 1;
	head++;
	head %= 1000;
	cost = bfs(queue[head][0], queue[head][1]);
	return cost;
}


int main()
{
	int n, cost=0;
	cin >> n;
	queue[tail][0] = n;
	queue[tail++][1] = cost;
	cout << bfs(n, cost);
}

orange4glace 7년 전 0

queue를 구현하는 과정에서 문제가 있는것같습니다.

현재 최대크기를 1000으로 잡으셨는데, 1개를 처리할 때 마다 3개씩 다시 추가로 들어오는 모양새라서,

앞쪽의 데이터가 처리되지 않았는데 새로운 데이터로 갱신이 되어서 문제가 발생하고있는듯 합니다.

queue의 크기를 [10000000][2] 로 잡으면 정답이 나오기는 하네요.

중복된 숫자를 제거하시는 방법으로 한번 생각해보시면 더 좋은 풀이가 될거라 생각합니다.

yih9329 7년 전 0

조언 감사합니다

생각을 못한 부분이네요

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

문제

문제

출처

ICPC

틀린 부분좀 찾아주세요

yih9329 7년 전 0

orange4glace 7년 전 0

yih9329 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말