제로베이스 20220427 코테 연습

1. 벌집

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

입력

• 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

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

풀이

import sys

N = int(sys.stdin.readline())

stair = 0
while True:
    stair += 1
    if N == 1:
        stair = 0
        break
    elif 3 * stair * (stair - 1) + 1 < N <= 3 * (stair+1) * stair + 1:
        break
        
print(stair+1)

채점 결과

• 정답

리뷰

• 다음과 같은 순서로 생각을 진행해서 풀었다.

  1. 1을 기준으로 한바퀴를 1층, 2바퀴를 2층..으로 정의한다.
  2. 한 층의 끝은 1,7,19,37,61...로 이루어진 수열이다.
     • 해당 수열은 6n을 계차로 하는 계차수열이다.
     • 이를 풀어쓰면 $1 + 6x + 6(x-1) + 6(x-2) + 6(x-3)…+ 6*2 + 6$이다.
     • 즉, 1 + 6 * (1~x까지의 합)으로 정리가 가능하고, 수식으로 $6 * \frac{x(x-1)}{2}$으로 표현 가능하다.
  3. 한 층의 범위는 이전 층의 끝~ 현재 층의 끝이다.
     • 즉, 3 * stair * (stair - 1) + 1 < N <= 3 * (stair+1) * stair + 1을 만족하는 수는 N층에 있다는 의미가 된다.
  4. N층에 있는 수까지 이동하는데 필요한 최소한의 거리는 N + 1이다.

더 나은 풀이

• 풀이 출처 : 아이디 rabi님의 풀이

print(int(-(-(3+(12*int(input())-3)**.5)//6)))

더 나은 풀이 리뷰

• 위에서 내가 풀었던 각 층의 끝값에 대한 수식을 극한으로 압축해두었다.

• 구하고자 하는 수를 x로 정의할때, 수식은 최종적으로 다음과 같이 전개된다.

  • $x = -\frac{-(\sqrt{(12N-3)}+3)}{6}$
  • $-6x = \sqrt{12N-3}+3 $
  • $-6x-3 = \sqrt{12N-3}$
  • $36x^{2} +36x + 9 = 12N-3$
  • $36x^2 +36x + 12 = 12N$
  • $3x^2+3x+1 = N$ (단, x는 정수)

• 위에서 구한 층 구하기와 같은 결과가 나옴을 알수 있다.

• 이차방정식의 해를 수식으로 나타낸 뒤, 그걸 한줄코딩으로 압축해놓은 결과물이었다.