1011 Fly me to the Alpha Centauri _python

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

1011번: Fly me to the Alpha Centauri

이게 왜 골드5?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

처음 풀땐 수식으로 풀릴것 같으면서도 그냥 구현해서 풀어보기로 했다.

양쪽에서 1빼고, 양쪽에서 2빼고, 양쪽에서 3빼고 이런식으로 계산하다가,

만약 x가 양쪽에서 4를 빼지 못한다면 4보다 작으면 1번, 4보다 크면 2번 이동하면 된다.

여기서 x가 1일수도 있고, 3일수도 있고, 5일수도 있지만, 이 문제는 이동하는동안 과정을 찾는게 아니라 단순히 횟수만 알면 된다.

그러니 x가 1일때 3에서 1로 줄어들지 못하니 틀린거 아닌가? 라고생각하더라도

3을 2로 줄이면 x가 2가되서 결과인 횟수에는 지장없다.

이걸 그대로 구현해봤는데 사실 이렇게 구현하다가 패턴이 보이긴 했다.

1 2 3 4 더해나가니까 n(n+1)/2라는 합공식에 *2를 했는 n(n+1)로 바로 결과가 나올것 같았다.

 

구현하면서 다른 블로그도 찾아봤는데

가장 설명이 좋았던 블로그...

https://eunhee-programming.tistory.com/99

 

1,2,3,3,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8... 이렇게 나오는데

1과 2는 1개씩, 3과 4는 2개씩... 

n*(n+1)로 계산을 했고 각 개수 1개씩 2개씩의 범위는 n*(n-1) +1 ~ n*(n+1)까지가 각 범위다.

그 중앙값인 n^2를 기준으로 작거나 같으면 n*2-1이고 크면 n*2이 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드 1 (그대로 구현)

import sys
input = sys.stdin.readline

"""
입력
for T:
    y-x를 양쪽에서 1,1빼고 2,2빼고 3,3빼고... 늘려나가서 횟수 세기.
    ==dis가 2(num)보다 크면 2(num)빼고, 4보다 크면 4빼고, 6보다 크면 6빼고... 만약 6보다 작다면?
    ==dis가 6(num)보다 작다면 -> 4((num+2)//2)보다 작거나 같으면 ans+=1, 4보다 크면 ans+=2
"""

T = int(input())
for i in range(T):
    #입력, 변수생성
    ans = 0
    num = 2
    x,y = map(int,input().split())
    dis = y-x

    #구현
    while dis>num:
        ans += 2
        dis -= num
        num += 2
    else:
        if dis > num//2:
            ans+=2
        else:
            ans+=1
    print(ans)

630ms

 

 

 

 

 

 

 

 

 

 

 

 

코드2

import sys
input = sys.stdin.readline

"""

"""

T = int(input())
for i in range(T):
    x,y = map(int,input().split())
    dis = y-x

    n=1
    while dis>n*(n+1):
        n+=1

    print(n*2 if n**2<dis else n*2-1)

440ms

생각보다 오래걸린다. 빠른사람은 56ms도 있던데