글 읽기 - 배열 사이즈를 어떻게 잡아야 하죠?

skysujun 7년 전 0

배열 사이즈를 169999 정도로 잡으면 정답이 뜨는데, 160001로만 해도 런타임에러가 납니다.

전 100001로 배열 크기를 잡으면 된다고 생각했는데, 왜 더 큰사이즈를 잡아줘야 되는지 , 그 기준이 뭔지 궁금합니다.

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

bool checker[169999];
int dat[169999][2];
int front, enda;


void push(int num, int cnt)
{
		dat[enda][0] = num;
		dat[enda][1] = cnt;
		enda += 1;
}

	void pop()
	{
		front += 1;

	}

	bool empty()
	{
		if (front == enda)
			return true;
		else
			return false;

	}

	int front_num()
	{
		return dat[front][0];

	}

	int front_cnt()
	{

		return dat[front][1];
	}



int main()
{

	

	int n, k;

	scanf("%d%d", &n, &k);

	for (int i = 0; i <= 100000; i++)
	{
		checker[i] = false;
	}

	push(n, 0);
	checker[n] = true;

	int num;
	int cnt;

	while (!empty())
	{
		 num =front_num();
		 cnt = front_cnt();

		pop();

		//printf("now : %d , cnt : %d\n", num, cnt);

		if (num != k)
		{
			if (checker[num - 1] == false && num > 0)
			{
				push(num - 1, cnt + 1);
				checker[num - 1] = true;
			}

			if (checker[num + 1] == false && num <= 99999 && num>=0)
			{
				push(num + 1, cnt + 1);
				checker[num + 1] = true;
			}

			if (checker[num * 2] == false && num <= 50000)
			{
				push(num * 2, cnt + 1);
				checker[num * 2] = true;

			}
		}

		else
		{
			goto outside;
		}

	}
	outside:
	printf("%d\n", cnt);
}

hun222y 7년 전 0

음 .. bfs를 구현하신거 같은데 bfs라는게 방문한 지점을 큐에 계속 넣어주는 방식으로 진행이 된다고 생각하시면 되는데 (큐를 사용하지않고 실제로 구현하신거 같은데 .. )

큐에 들어갈때 중복되는 경우도 일단 넣어놓고 판별을하는 경우라서 ...

예를들어 5 에서 부터 시작을 하게되면 배열에 4 ,6 ,10 이 동시에 들어가게 되는데 그 4 6 10 에 대해서 또 3개씩 배열에 넣다보면 배열의 크기가 100000의 개수를 넘어가게 되는 경우가 발생하셔서 그러신거 같아요

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

문제

문제

출처

ICPC

배열 사이즈를 어떻게 잡아야 하죠?

skysujun 7년 전 0

hun222y 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말