Baekjoon 알고리즘 문제풀기

[2292] 벌집

문제

• 위의 그림에서 입력으로 주어진 숫자까지 가는 최단거리를 출력하는 프로그램을 작성
• 예시
  • 13 입력 시 3
  • 58 입력 시 5
• 점화식을 세워서 풀었다.
  • 육각형의 4시방향 숫자는 1, 7, 19, … 이므로, $a_{n+1}=6\times(n-1)+a_{n}$ 의 관계를 보인다.
  • 계차수열 $b_{n}$은 $b_{n}=a_{n+1}-a_{n}=6n$ 으로 정의된다.
  • 따라서,
    • $a_{n}=a_{1}+\sum_{k=1}^{n-1}b_{k}=1+\sum_{k=1}^{n-1}6k$
    • $a_{n}=1+6\sum^{n-1}_{k=1}k = 1+6\frac{(n-1)\times n}{2}$
    • $a_{n} = 1+3(n-1)\times n$
    • ∴ $a_{n}= 3n^{2}-3n+1$
• 이를 이용하여 풀이를 하면 아래와 같다.

정답

num = int(input())

def find_num(n):
    cnt = 0
    if n==1:
        return 0
    else:
        while True:
            cnt += 1
            r_p = 3*pow(cnt,2)-3*cnt+1
            r_n = 3*pow(cnt+1,2)-3*(cnt+1)+1
            if n>r_p and n<=r_n:
                return cnt
cnt = find_num(num)
print(cnt + 1)