백준 1011 파이썬- Fly me to the Alpha Centauri

Intro

---

백준 기본수학1에서 solved.ac 티어 기준으로 골드5이며 이전 문제들은 모두 브론즈임을 감안하면 상당히 어려운 수준인 것 같다. PS 초보인 나는 1193 문제를 풀 때 수열을 써서 똑같이 풀었기에 많이 어렵진 않았다. 

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

---

거리에 따른 장치 작동 횟수

이 표를 보면 규칙이 눈에 보인다. 색깔별로 n군을 잡아보면 첫번째 군은 안에 개수가 2개, 두번째 군은 4개, 세번째 군은 6개 이렇듯 n군 안에 총 2n개가 들어있다. 이를 이용하여, 거리가 어느 군에 있는지를 구했다. 이렇게 n을 구한 후 각 군을 잘 보면 딱 반으로 나뉘는 것을 볼 수 있다. 이를 이용하여 거리가 군에서 과반을 넘어가면 2n을 출력 , 그렇지 않으면 2n - 1을 출력했다 ! 

 

 

Python 코드

import sys

n = int(sys.stdin.readline())
TestLIST = []
for i in range(n):
    TestLIST.append(list(map(int, sys.stdin.readline().split())))


def adsf(list):
    x = list[0]
    y = list[1]
    gap = y - x
    i = 0
    while 1:
        if i * (i + 1) / 2 - 2 * i <= gap <= i * (i + 1):
            break
        else:
            i += 1
    if i * (i + 1) >= gap > i * (i + 1) - i:
        return 2 * i
    else:
        return 2 * i - 1


for a in TestLIST:
    print(adsf(a))