백준2292번 : 벌집 (C++)

처음 쓰는 velog #1
출처 : https://www.acmicpc.net/problem/2292

문제 풀다가 '틀렸습니다' 7번에 '컴파일 에러' 2번 났다.ㅠㅠ
어제 밤에 풀다가 덮고 아침에 그림 새로 그렸더니 식을 도출했다.

아유 그림이 화면 가득하게 나오네

> 문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

말로 하는 설명

위 그림을 보면 1에서부터 아래로 1 증가, 그 다음은 1을 중심으로 시계방향 원을 그리며 1을 감싸고 돈다.

7까지 첫번째 원 완성. 그 다음은 7에서 아래로 1칸 이동해서 또 시계방향 원을 그리며 첫번째 원을 감싸고 도는 두번째 원 완성.

숫자가 1씩 증가해 원이 완전해지는 지점을 살펴보면 1, 7, 19, 37, 61 이렇게 커지는데. 1부터 +6, +12, +18, +24 가 되는 것을 알 수 있다. 즉 6의 배수만큼 커지면서 원을 새로 생성한다. 애초에 벌집이 육각형인것에서부터 눈치를 챘어야 했나 암튼

1, 7, 19, 37, 61... 을 식으로 표현해본다면
1, 1+(6x1) , 1+(6x1+6x2), 1+(6x1+6x2+6x3), 1+(6x1+6x2+6x3+6x4) 요런 식으로 표현할 수 있다.

1+(6x1+6x2+6x3+6x4) 요걸 떼어와서 일반식으로 표현해보면 1+6(1+2+3+4) 가 된다.
1부터 n까지 더하는 공식은 n(n+1)/2 이므로 1+6(1+2+3+4) = 1+6x{4x(4+1)/2} = 61

결국 1, 7, 19, 37, 61... <- 요건 3n(n+1)+1 로 표현할 수 있다.
여기까지 이해가 된다면 바로 코드로 >>

이해가 안됐어요? 괜찮아요

1은 뭐 시작한 방이니까 1개일거고(시작한 방까지 포함해서 센다) 7보다 작거나 같은 숫자라면 1번 방 외에 한칸 더 움직여야 그 방으로 이동할 수 있으므로 2개의 방을 지나간다.

19보다 작거나 같은 숫자라면, 1을 둘러싼 2번째 원이므로 1 외에 두 칸을 더 움직여야 해당하는 숫자의 방으로 이동할 수 있다. 1+2 = 3개의 방을 지나가야 한다는 말

19는 1+(6x1+6x2+6x3) -> 3n(n+1)+1 여기서 n에 2를 대입한 값이고, 1을 포함하여 3개의 방을 지나야 도달할 수 있는 곳!

7보다 크고 19보다 같거나 작다면 3개의 방을 이동해야 한다. 따라서 n+1 개의 방을 이동하면 된다.

아래에 요 식을 그대로 쓴 코드가 있다.

코드(C++)

#include <iostream>
using namespace std;

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

	for (int i = 0;; i++)
	{
		if (a <= 3 * i * (i + 1) + 1)
		{
			cout << i + 1;
			return 0;
		}
	}	
}

성공이얌