[알고리즘] 백준 1011

백준 1011 파이썬

Distance (거리)	Route(경로)	Count(경로의 개수)	Move Distance (경로의개수가 같은것의 합)	Max Distance (주어진 경로의 개수에서 이동 최대값)
1	1	1	1	1
2	1 1	2	1	2
3	1 1 1	3	2	4
4	1 2 1	3
5	1 2 1 1	4	2	6
6	1 2 2 1	4
7	1 2 2 1 1	5	3	9
8	1 2 2 2 1	5
9	1 2 3 2 1	5
10	1 2 3 2 1 1	6	3	12
11	1 2 3 2 2 1	6
12	1 2 3 3 2 1	6

1. 규칙찾기

위 문제는 규칙찾는게 가장 어렵고, 그 다음이 코드구현이었다.

우선 거리 별 경로를 찾고, 경로의 개수를 센다. 이후 경로의 개수(count)가 같은것의 개수를 Move distance라 한다.

또, Move distance가 같은값들끼리 더한값은 경로의개수 별로 이동할 수 있는 최대 거리를 의미한다.

즉, 이 문제에서 집중해야하는것은 아래의 규칙이다.

이동을 한다 = 경로의 개수(count)가 하나씩 생긴다 = 이동할 수 있는 최대거리를 벗어난다

이동을 한다는것은 이동할 수 있는 최대거리, 즉 같은값들끼리 더한 Max distance를 벗어난다는 이야기이다.

이해가 안가도 괜찮다. 왜냐면 나도 이해하기 어려웠으니까..ㅋㅋㅋㅋㅋㅋ

 

예를들면, 0-3만큼 이동을 한다고 치면,

이동거리 : 3

경로 : 1 1 1

경로의 개수 : 3

move distance : 2

최대이동값 : 4

내가 출발하는 시점에서 최대이동값의 범위 안에 3이 없다면, 계속해서 이동을 해줘야한다.

 

행위	이동거리	이동횟수	이동할 수 있는 최대 거리
0에서 우주선 작동 1 도착	1	1	1
1에서 이동 2 도착	1	2	2
2에서 이동 3도착	1	3	4

코드구현

case = int(input())

for i in range(case):
    x, y = map(int, input().split())
    distance = y - x
    count = 0  #이동횟수
    move = 1  # 1만큼 이동하는건 작동하는순간 무조건 일어나는 일이기 때문.
    move_distance = 0
    while move_distance < distance:  #최대 이동거리 < 이동하고자하는 거리 를 벗어나면 이동이 발생
        count += 1  #이동 발생
        move_distance += move  # 이동발생 시, 최대이동거리도 늘어남
        if count % 2 == 0:
            move += 1   # 이동횟수가 짝수가 될 때 마다 move distance값이 1씩 오름
    print(count)

 

 

이 문제에 여러가지 규칙이 있고, 푸는방법도 여러가지이지만... 정말 이해하기 어려운 문제였기 때문에 기록으로 남긴다.

다른분들에게도 도움이 되었으면 좋겠다.