[백준알고리즘] 1011번: Fly me to the Alpha Centauri -Python, C++

[백준알고리즘] 1011번: Fly me to the Alpha Centauri -Python, C++

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

1011번: Fly me to the Alpha Centauri

20210117 아래 C++ 코드랑 설명을 추가했다. 과거 설명은 지금 봐도 모르겠다.

---

2주 정도 전에 풀려고 시도했다가 포기했었던 문제다. 그러다가 괜찮은 코드를 보게 되었었다.

claude-u.tistory.com/50

 

이번에 풀면서는 저분의 코드를 까먹고 풀었었지만 어떻게 하다 보니 똑같이 구현하게 되었다.

저번에 포기를 하고 나서.... 규칙을 찾아야 한다는 것은 기억을 하고 있었다. 그래서 이런저런 규칙들을 찾았다. 다양한 규칙들을 찾았는데 실제로 코드에 적용하기를 고민하다가 이 방법으로 풀었었다.

 

우선, 두 지점 사이의 거리를 통해 이동할 수 있는 횟수를 나열해보겠다.

# 거리 : 이동방법 -> (이동 횟수)
1 : 1 -> (1)
2 : 1, 1 -> (2)
3 : 1, 1, 1 -> (3)
4 : 1, 2, 1 -> (3)
5 : 1, 2, 1, 1 -> (4)
6 : 1, 2, 2, 1 -> (4)
7 : 1, 2, 2, 1, 1 -> (5)
8 : 1, 2, 2, 2, 1 -> (5)
9 : 1, 2, 3, 2, 1 -> (5)
10 : 1, 2, 3, 2, 1, 1 -> (6)
11 : 1, 2, 3, 2, 2, 1 -> (6)
12 : 1, 2, 3, 3, 2, 1 -> (6)
13 : 1, 2, 3, 3, 2, 1, 1 -> (7)
....

 

코드에 사용한 규칙은 이동 횟수에 있다. 1번 이동하는 경우 1, 2번 이동하는 경우 1, 3번 이동하는 경우 2, 4번 이동하는 경우 2, 5번 이동하는 경우 3, 6번 이동하는 경우 3,....

 

즉, 길이가 1, 2인 경우 1번, 3, 4인 경우는 2번, 5, 6인 경우는 3번씩 등장하는 것이다. 마찬가지로 7, 8인 경우에는 4번씩 등장하는 것을 구할 수 있다.

 

이러한 개념을 그대로 코드에 사용했다.

 

아래는 길이가 저렇게 되는 이유?를 수학적인 식은 아니지만 나름 생각했던 내용이다. 내용이 지저분하다.

두 지점의 거리가 6인 경우를 우선 보게 되면 이동 방법은 1, 2, 2, 1으로 4번의 이동을 하게 된다. 도착 시에는 거리가 1이어야 하기 때문에 좌우 대칭적인 구조를 갖게 되며 이 경우에는 이동 횟수가 짝수이다. 이 경로에서 한 번에 최대로 이동할 수 있는 거리는 2이다.

 

여기서 거리가 7, 8, 9인 경우를 생각하게 되면, 이 거리가 6인 경로에서 각각 1, 2, 3의 이동거리를 추가한 경로가 된다. 따라서 6의 이동 횟수 +1만큼의 이동 횟수가 되는 것이다.

또한, 6을 구성하는 이동거리의 최대인 2보다 1 큰 3까지만 경로를 구성하는 데 사용할 수 있게 된다.

마찬가지로 거리가 10, 11, 12인 경우에는 6인 경로에서 각각 3+1, 3+2, 3+3의 이동거리를 추가한 경로가 된다. 따라서 6의 이동 횟수 +2만큼의 이동 횟수가 되는 것이다.

 

그리고 12는 또다시 1, 2, 3, 3, 2, 1의 경로로 좌우 대칭적이면서 이동 횟수가 짝수인 경로가 만들어진다.

따라서 여기서도 마찬가지로 13, 14, 15, 16은 12의 이동경로에서 +1, +2, +3, +4가 된 경로이며, 17, 18, 19, 20은 4+1, 4+2, 4+3, 4+4의 이동경로가 된다.

또한 12를 구성하는 한 번에 이동하는 최대 이동거리인 3보다 1 큰 4만큼 경로를 구성하는 데 사용할 수 있다.

 

for _ in range(int(input())):
    x, y = map(int, input().split())
    dist = y-x

    s, t, c = 0, 1, 0
    while s < dist:
        s += t
        c += 1
        if s < dist:
            s += t
            c += 1
        else:
            break
        t += 1
    
    print(c)

 

음 위의 저 설명을 어떻게 이해했는지 과거의 나는 대단한 것 같다;

 

코드 로직은 똑같은 데 지금은 더 간단하게 생각했다.

 

그냥 간단히 좌, 우에서 하나씩 같은 거리만큼 다가오게 했다. 여기서 한쪽씩 번갈아서 이동하면서 만나거나 지나치는 순간 양쪽의 총 이동 횟수를 고려한다고 생각하면 될 것 같다.

 

단순히 거리가 \(11\) 떨어져 있다고 생각을 했을 때, [1, 2, 2, 3, 2, 1] 이 이동하는 경로 중 하나일 것이다. 하지만 [1, 2, 3, 3, 2, 1]로 고려하고 지나쳤으니 만났다고 생각을 한다는 것이다.

가능한 큰 수가 포함될수록 이동 횟수는 더 줄어들 것이라 생각했고, 양쪽에서 대칭일 때가 가장 이동 횟수가 적다고 생각을 하고 풀었다.

 

수많은 방법 중에 x와 y의 범위만 \(2^31\) 이라 동적 계획법으로 푼다느니 하는 생각을 했다가 접었다. (메모리 제한도 512MB 라 당연히 안된다.)

 

아무튼 그렇게 간단하게 생각하고 풀었더니 됐고, 애를 먹은 게 아래 코드에서 \(curr\)의 자료형이다.

위에서 말했듯이 거리가 \(11\) 일 때도 \(12\) 의 최소 이동거리인 [1, 2, 3, 3, 2, 1]을 고려하듯이 \(dist\)의 거리가 \(2^31\) 일 때 \(curr\)는 \(dist\)의 범위를 넘을 수도 있다. 즉, int 형의 범위인 [\(-2^31\), \(2^31\)) 을 넘게 될 수 있다.

 

그래서 unsigned int 형으로 바꿔주어서 문제를 해결했다.

#include <iostream>

void solve(void);

int main(void)
{
	int test_case;
	std::cin >> test_case;

	for (int t = 0; t < test_case; t++)
		solve();
}

void solve(void)
{
	int x, y;
	std::cin >> x >> y;

	int dist = y - x;
	uint32_t curr = 0;
	int step = 1;
	int count = 0;

	while (curr < dist)
	{
		curr += step; count++;

		if (dist <= curr) break;

		curr += step; count++;

		step++;
	}

	std::cout << count << std::endl;
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다