백준 2292번 - 벌집

https://www.acmicpc.net/problem/2292

2292번: 벌집

우선 나의 사고는 이랬다. 해당 수를 입력받고 현재 1, 2, 8 , 20이 경계이므로 해당 수 보다 커질 시점에 해당 인덱스를 출력시키면 되었다.

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

int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n;
	cin >> n;
	int limit = (int)10000000;
	vector<int> vec(limit);
	vec[0] = 1; vec[1] = 2;
	if (n == 1)
	{
		cout << 1;
		return 0;
	}
	for (int i = 2; i < limit; i++)
	{
		vec[i] = vec[i - 1] + (6 * (i - 1));
		if (n < vec[i])
		{
			cout << i;
			break;
		}
	}
	


	return 0;
}

하지만 메모리를 너무 잡아먹는다.

심지어 limit의 크기가 커져서 메모리 초과도 자주 났다. 정답은 결국 저렇게 해서 나오긴했지만.. 뭔가 아쉽다.

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

int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n, layer = 0;
	cin >> n;
	if (n == 1)
		layer = 1;

	for (int sum = 2; sum <= n; layer++)
		sum = sum + (6 * layer);

	cout << layer;
	
	return 0;
}

그래서 반복문 갯수를 줄여보려고 생각해봤고,

각 겹의 끝 값이 1 , 7 , 19 , 37 이렇게 ( + 6, + 12, + 18 ...) 임을 이용했다.