BOJ 2155번: 삼각형의 최단 경로

https://www.acmicpc.net/problem/2155

2155번: 삼각형의 최단 경로

문제풀이:

어떻게 풀어야 하는 지 도무지 모르겠었는데..(사실 생각하기 귀찮아서 미뤄뒀던 걸수도..)

동아리 부원이 푼 걸 보고 힌트를 얻었다!

엄청난 삽질.. 까진 아니고 알고 나니 아.. 하는 그런 문제였다. 이렇게 푸는 게 정석일 지는 모르겠지만..

 

루트 즉, 1번 위치부터 각 번호까지의 최단 경로를 구해보면

0

2 1 2

4 3 4 3 4

6 5 6 5 6 5 6

이렇게 나온다! 이 규칙은 쉽게 구할 수 있으니 이렇게 구해서 큰 수에서 작은 수를 빼주기만 하면 되는 것..

 

import sys
import math

def findLevel(x):
    level = math.ceil(x**0.5)
    if (((x - ((level-1)**2+1)) % 2)==0):
        return 2*(level-1)
    else:
        return 2*(level-1)-1

A, B = map(int, sys.stdin.readline().split())
a = min(A, B)
b = max(A, B)

levA = findLevel(a)
levB = findLevel(b)
print(levB-levA)