[Silver IV] 벌집 2 - 27436

문제 링크

성능 요약

메모리: 31256 KB, 시간: 48 ms

분류

이분 탐색, 수학

문제 설명

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

입력

첫째 줄에 N(1 ≤ N ≤ 9 × 1018)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

---

풀이

아이디어

위 벌집은 다음 수식을 따른다
$\sum_{n=1}^{1e18}6n$일때 $n$

즉, 이를 정리해서 이분탐색해 $3n(n-1) + 1$을 넘지 않는 $n$의 값을 찾는것인데 이를 코드로 구현하면 아래와 같다

코드

N = int(input())
start, end = 1, 100000000000001
calc = lambda x: 3 * x * (x - 1) + 1

while start <= end:
    mid = (start + end) // 2
    if calc(mid) >= N:
        end = mid - 1
        temp = mid
 
    else:
        start = mid + 1
print(int(temp))

---

회고

end=1e18로 두고 풀었을때 아래의 경우 오류가 발생한다.

# input
7782220160928055297

# output
1610612737

# answer
1610612738

사실 이유는 모르겠다. 범위 문제인지 부동소수점 오류 문제인지인데 아마 부동소수점 오류라고 추측하고 있다.