이번 문제는 알고리즘이라기 보단, 수학을 이용하는 문제였다.
처음에 이 문제를 접근했을때, 2^31이라는 0 ≤ x < y < 2^31 조건을 보자마자, 그냥은 불가능하다고 생각했다.
처음에 그래서 든 생각이 DP를 써야되나? 싶었다.
왜냐하면 0부터 5까지 가야한다고 치자.
맨 처음 0에서 1까지 무조건 이동해야한다. 그 다음 1에서 선택할 수 있는 선택지는 0,1,2이다. 0은 빼고 1,2이니까 재귀로 계속 부르면서
1 -> 2(1칸이동) -> 1,2중에서 선택해서 계속 탐색
1 -> 3(2칸이동) -> 1,2,3중에서 선택해서 계속 탐색
이런식으로 하려했다.
이런식으로 이동 횟수를 누적해가면서 DP배열에다가 넣고 그 다음에 만약 DP에 저장된것보다 크면 return을 통해서 나가기
이런식으로 경우의 수를 줄이려 했다.
그런데, 생각해보면 그러면 DP배열을 y최댓값인 2^31까지 해야하는데 이것또한 불가능하다.
어? DFS로 그러면 이동횟수를 누적해가면서 계산해야하나? 싶었는데 이것도 말이 안되는게 어쨋든 visited를 갱신하려면 배열이 있어야하는데 이것도 불가능했다.
결국 답을 보고 풀었다.
해설
핵심은 문제의 마지막에 있었다. 목적지에 도착하기전에는 무조건 이동거리가 1이어야한다는 것이다.
만약 10에 도착하려면 무조건 9 -> 10으로 이동해야한다.
그렇다면 9에 도착할 수 있는 최대 이동거리는 몇일까 바로 2이다.
왜냐하면 2의 이동거리로 9를 도착해야 9에서 1,2,3의 경우의수에서 1을 골라 10으로 도착할 수 있기 때문이다.
만약 그럼 7에서는 어떨까? 바로 3의 최대거리로 도착해야 2,3,4중에서 2를 선택할 것이다.
고로 이러한 규칙을 생각해보면
1+2+1 최대 이동거리 4
1+2+3+2+1 최대 이동거리 9
1+2+3+4+3+2+1 최대 이동거리 16
...
이런식이 최대 이동거리가 될 것이다.
이래서 알고리즘이 수학인것이다.
만약 그렇다면 이동해야하는 이동거리가 12인데 최대 이동거리가 9이면 어떻게 할까?
1+2+3+2+1에다가 3을 그냥 끼워넣으면 된다.
1+2+3+3+2+1 그리고 이동횟수를 1증가시키면된다.
만약에 더 이동해야하는 이동거리가 3보다 이하라면 그냥 이동거리를 끼워넣고 이동횟수를 1 증가시키면 된다.
그런데 만약 이동거리가 13인데 최대 이동거리가 9이면 어떻게 할까?
1+2+3+2+1에서 3을 넣고 1을 더 이동해야할것이다.
이러면 결국 4/3이 1.3333이니까 0.333에 해당하는만큼 한번 더 움직여야하므로 2번을 이동을 더하면된다.
코드
#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
int num = 0;
cin >> num;
for (int i = 0; i < num; i++) {
long long Answer = 0;
//N은 최대 이동거리
long long N = 0;
long long start = 0;
long long end = 0;
cin >> start >> end;
while (N * N <= end-start) {
N++;
}
N--;
Answer = 2 * N - 1;
long long extra = (end - start) - (N * N);
if (extra == 0) {
//최대거리로 정확히 도착가능
cout << Answer << "\n";
}
else {
//최대거리안에 갈수 있음
if (extra <= N) { Answer++; }
else {
//만약 13광년인경우 N이 3이다. (13-0)-3*3 = 4로 추가로 4만큼 더가야함
//4/3 = 1.3333 -> 올림 이므로 2
extra = (long long)ceil((double)extra / (double)N);
Answer += extra;
}
cout << Answer << "\n";
}
}
return 0;
}