[백준] 2292 - 벌집 구조

문제: www.acmicpc.net/problem/2292

2292번: 벌집

 

 

한 칸씩 움직일 때마다 숫자가 1씩 증가한다.

 

한 바퀴 돌 때마다 움직여야 하는 횟수가 6씩 증가한다.

 

따라서 바깥으로 한 칸씩 움직일 때 지나는 수들은 계차수열이다.

 

이때 육각형이므로 계차는 6이다.

 

따라서 아래와 같은 수열을 생각해보자

2 + n(n-1)/2 * 6 = 2 + 3n(n-1)
Bn = 7 + (n(n+1)/2 - 1) * 6

시계방향으로 육각형을 감싸 돌며 더 큰 육각형이 생길 때,

 

그 육각형의 시작점과 끝점은 각각 수열 An과 Bn으로 나타난다.

 

따라서 N번 방에 가기 위해 지나치는 방의 개수의 최솟값은

 

An <= N <= Bn 을 만족하는 n에 대해, n + 1이다.

 

실제로는 An = N인 경우는 극히 드물지만, An = N이라고 가정하고 n을 구해보자.

 

하지만 실제로는 N이 An보다 크거나 같기 때문에, 저기서 구한 n은 실제로 구하려는 n보다 항상 크거나 같다.

 

따라서 구하는 n은, 위 식에서 나온 n을 내림한 값이다.

 

코드:

 

주의:
1. N의 범위가 1000000000까지기 때문에 n을 int로 선언하면 오버플로우가 난다.
2. cout 함수는 소수점이 너무 많으면 그냥 반올림해버린다.