[1011] Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

<문제>

풀이를 이끌어내는데에 필요한 결정적인 관찰중 하나는, 제곱수에 관한 것이다.

1, 4, 9, 16...같은 제곱수는 아래와 같은 형식으로 딱 떨어진다.

1
1-2-1
1-2-3-2-1
1-2-3-4-3-2-1

움직여야 하는 거리, 곧 문제에서 주어지는 (y-x)를 len이라고 하자.

len이 16이라면 최대 이동속도는 4이므로, (4-1)*2+1, 곧 7을 답으로 구할 수 있다.

최대 이동속도는 정가운데에 존재하고, 정가운데를 기준으로 양옆에 1...maxSpeed-1개의 숫자가 있을테니

len이 제곱수라면 sqrt(len)으로 maxSpeed를 구한 뒤, 2*(maxSpeed-1)+1을 출력하면 된다.

 

문제는 [17, 24]같은 제곱수 사이에 존재하는 대부분의 경우를 어떻게 처리하느냐인데...

"1-2-3-4-3-2-1"에 숫자를 끼워넣는다고 생각해보자.

물론 이경우 maxSpeed가 4이므로, 4를 초과하는 숫자를 넣을수 없으며

음수와 0을 끼워넣는 경우는 최적해를 보장할 수 없으므로,

[1, maxSpeed]사이의 수를 끼워넣는다고 생각하면 되겠다.

 

2를 끼워넣으면 "1-2-3-4-3-2-2-1"이나 "1-2-2-3-4-3-2-1"처럼 2가지 경우의 수가 있고,

여기서 다시 2를 추가하는 경우도 다시 2가지가 그대로 유지된다.

결국 어떠한 방식으로든 [1, maxSpeed]사이의 수를 끼워넣는것은 항상 가능하며

최대한 적은 개수를 추가하기 위해 가장 큰 수부터 끼워넣는다면(그리디적 접근)

추가횟수 : (len - (maxSpeed*maxSpeed)) / maxSpeed의 식이 나오게 된다.

 

 

len : 공간이동 장치가 움직여야하는 총 거리

maxSpeed : 공간이동장치가 움직일때의 최고속력

ans : 최소 이동횟수

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int t;
int main(void) {
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        int len = y - x;
        int maxSpeed = sqrt(len) + 1e-3;
        int ans = 2 * (maxSpeed - 1) + 1;
        int cur = maxSpeed * maxSpeed;
        int left = len - cur;
        ans += (int)(ceil((double)left / (double)maxSpeed));
        cout << ans << '\n';
    }
    return 0;
}