[Baekjoon] 1011번 : Fly me to the Alpha Centauri

 

골드 5

문제 링크(페이지) : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

👇 문제 펼치기

 

문제 풀이

1부터 주어진 조건에 맞도록 횟수를 세고, 규칙을 파악한다.

총 거리	이동 과정	작동 횟수	반복 횟수
1	1	1	1
2	11	2	1
3	111	3	2
4	121	3	-
5	1211	4	2
6	1221	4	-
7	12211	5	3
8	12221	5	-
9	12321	5	-
10	123211	6	3
11	123221	6	-
12	123321	6	-
13	1233211	7	4
14	1233311	7	-
15	1233321	7	-
16	1234321	7	-
17	12343211	8	4
18	12343221	8	-
19	12343321	8	-
20	12344321	8	-

 

표를 보면 1-2-3-3-4-4-5-5-5... 로 규칙적으로 증가하고 있음을 알 수 있다.

 

반복 횟수는 1-1-2-2-3-3... 이런 식으로 두번 씩 반복되고,

반복 횟수마다 이동할 수 있는 최대 거리는 해당 거리(x)까지의 반복횟수를 모두 더한 것과 같다.

예를 들어 3번으로 이동할 수 있는 최대 거리는 12(1+1+2+2+3+3) 이다. 

 

이 규칙을 이용해 코드를 짜면 다음과 같다.

 

코드

t = int(input())

for _ in range(t):
    x, y = map(int, input().split())
    distance = y - x # 이동거리
    count = 0 # 작동 횟수
    again = 1 # 반복 횟수 (처음엔 1회)
    position = 0 # 이동 위치

    while position < distance :
        count += 1
        position += again  # count 수에 해당하는 반복 횟수를 더함
        if count % 2 == 0 :  # count가 2번 반복될 때 마다 반복횟수 증가
            again += 1
    print(count)

 

느낀점

방법이 쉽게 떠오르지 않을 때는 직접 하나씩 적어보면서 규칙을 파악해 보자.