이번 문제는 백준의 골드 5 문제이다.
문제 이름이 조금 길어서 생략하도록 한다.
이번 문제는 조금 수학적인 문제인 것 같다.
k광년을 매번 이동하는데, 다음 이동은 k-1, k, k+1
위의 세 가지 선택지 중 하나밖에 고르지 못한다.
또한, 처음과 마지막 이동은 반드시 1광년만 이동하도록 한다.
모든 경우의 수
거리 별로 경우의 수들을 한 번 모두 적어보도록 하자.
- 4광년을 가야 하는 경우
1 2 1을 고르면3일 만에 갈 수 있다. - 8광년을 가야 하는 경우
1 2 2 2 1을 고르면5일 만에 갈 수 있다. - 9광년을 가야 하는 경우
1 2 3 2 1을 고르면5일 만에 갈 수 있다. - 11광년을 가야 하는 경우
1 2 3 2 2 1을 고르면6일 만에 갈 수 있다. - 12광년을 가야 하는 경우
1 2 3 3 2 1을 고르면6일 만에 갈 수 있다. - 16광년을 가야 하는 경우
1 2 3 4 3 2 1을 고르면7일 만에 갈 수 있다.
위에 적은 경우들을 잘 살펴보면 특징을 하나 발견할 수 있다.
N^2의 경우에는 N*2 - 1일 만에 갈 수 있다는 것이다.
이후로 몇 개의 경우를 더 적어보도록 하자.
- 17광년을 가야 하는 경우
1 2 3 4 3 2 1 1을 고르면8일 만에 갈 수 있다. - 18광년을 가야 하는 경우
1 2 3 4 3 2 2 1을 고르면8일 만에 갈 수 있다. - 19광년을 가야 하는 경우
1 2 3 4 3 3 2 1을 고르면8일 만에 갈 수 있다. - 20광년을 가야 하는 경우
1 2 3 4 4 3 2 1을 고르면8일 만에 갈 수 있다. - 21광년을 가야 하는 경우
1 2 3 4 4 3 2 1 1을 고르면9일 만에 갈 수 있다.
위의 몇 개의 경우들을 더 살펴보면, 새로운 특징을 발견할 수 있다.
N^2을 기준으로, N^2의 경우에는 N*2 - 1이 된다.
N^2을 기준으로 더 큰 경우에는, N*2가 된다.
그리고, N^2 + N을 기준으로 더 큰 경우에는, N*2 + 1이 된다.
즉, 우리가 가장 먼저해야 할 일은 거리를 구하는 것.
이후에 해당 거리가 어떤 수의 제곱 수와 가까운 지 찾아야 한다.
최종 구현 코드는 아래와 같다.
#include <iostream>
#include <cmath>
using namespace std;
int earth = 0, centauri = 0, num = 0, answer = 0;
int main() {
cin >> num;
for (int i = 0; i < num; i++) {
cin >> earth >> centauri;
int distance = centauri - earth;
if (distance < 1)
// 거리가 1보다 작으면 시간이 안걸린다.
cout << 0;
else {
int square_root = sqrt(distance);
// 여기서 가장 가까운 제곱근을 찾는다.
if (distance == (square_root * square_root))
answer = (square_root * 2) - 1;
// N^2 기준, 동일할 시 N*2 - 1
else if (distance <= (square_root * square_root) + square_root)
answer = (square_root * 2);
// N^2 ~ N^2 + N 사이의 수는 N * 2;
else
answer = (square_root * 2) + 1;
// N^2 + N ~ (N+1)^2 까지는 N * 2 + 1;
}
cout << answer <<'\n';
}
return 0;
}역시 이런 수학 문제나, DP 문제들은 모든 경우의 수를
직접 다 적어보는 게 문제를 빨리 푸는 방법인 것 같다.