반응형
https://www.acmicpc.net/problem/1011
💡 Fly me to the Alpha Centauri
✅ 문제 풀이
- 시작지점 x와 끝지점 y의 사이 거리를 구하고, 그 거리는 최소 몇번의 이동이 필요한지 구한다.
- 무조건 처음시작과 마지막 이동은 1씩 이동한다. 따라서 y-x에서 2(처음, 끝)를 뺀 거리만을 가지고 몇번 이동할 수 있는지 구하면 된다.
- 만약 y-x-2의 결과가 0 이하라면, 즉 y-x가 1 또는 2 였다면, 시작과 끝을 제외하고는 중간에서 이동하는 거리가 없기 때문에 1이면 1번 이동하는것이고, 2이면 2번 이동하는 것이된다.
- 다음과 같은 수학적 규칙에 따라 거리마다의 최소 이동 횟수를 구할 수 있다.
- 시작과 끝의 각각 1만큼의 이동 거리를 빼고 생각해보자.
- dis = y-x-2 일때, dis가 1일때부터 이동 횟수를 구해보자. 이때 처음이 1이고, 마지막도 1이었기 때문에, 시작도 마지막도 (0,1,2)에서 고를 수 있게 되어야 한다.
- 1 : 1 => 1
2 : 2 => 1
3 : 1,2 => 2
4 : 2,2 => 2
5 : 1,2,2 => 3
6 : 2,2,2 => 3
7 : 2,3,2 => 3
8 : 2,2,2,2 => 4
9 : 2,3,2,2 => 4
10 : 2,3,3,2 => 4
11 : 2,3,3,2,1 => 5
12 : 2,3,3,2,2 => 5
13 : 2,3,3,3,2 => 5
14: 2,3,4,3,2 => 5
15 : 2,3,4,3,2,1 =>6
16 : 2,3,4,3,2,2 => 6
17 : 2,3,4,3,3,2 => 6
18 : 2,3,4,4,3,2 => 6
...
보면, 규칙이 있는걸 확인할 수 있다.
이동횟수가 1인게 2개, 2인게 2개, 3인게 3개, 4인게 3개....
두 묶음씩 동일한 이동횟수를 갖는 dis의 개수가 하나씩 늘어나고 있다.
(이동 횟수) => dis의 개수 로 따지면
(1,2) => 2+2
(3,4) => 3+3
...
dis의 개수가 같은 것끼리 묶어보면, 4, 6, 8, 10 ...이렇게 늘어나는 것을 알 수 있다.
이를 누적하면 4, 10, 18, 28....인데, 이 수열을 수식으로 나타내보면 다음과 같다.
a1 = 4
a2 = a1+(a1+2)
a3 = a1+(a1+2)+(a1+2+2)
a4 = a1+(a1+2)+(a1+2+2)+(a1+2+2+2)
...
an = n*a1+n(n-1) = n*n+3n 으로 정리할 수 있다. - 이제 dis와 n^2+3n 을 가지고, n=1부터 계산하여 n^2+3n이 dis보다 작으면 n을 늘리고 dis보다 커지면 해당 n을 통해 이동 횟수를 구할 수 있다. 이는 while 문으로 n을 결정할 수 있다
- 이동횟수가 {1,2}인것부터 n=1이고, 그 뒤로 한 묶음씩 n을 늘려가면 된다.
- 예를 들어 dis가 15이면 n=3임을 구할 수 있는데, n*2를 한 6과 n*2-1를 한 5 둘 중 하나가 15의 최소 이동횟수 후보가 된다.
- 근데 n^2+3n-n인 n^2+2n보다 dis가 작으면 n*2-1에 해당하는 5가 답이 되는것이고, 그렇지 않으면 n*2에 해당하는 6이 답이 되는 것이다.
- 따라서 이러한 수학적 규칙과 식을 이용하여 이동 횟수를 쉽게 구할 수 있다.
- 이 문제에서 주의할 점은, 입력으로 주어지는 x와 y의 범위가 2^31까지 이기 때문에, int로 받아 계산하면 안되고, long long으로 받아 계산하여야 한다는 점이다.
✏ 코드 전문
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
for (int i = 0; i < t; i++) {
long long s, e;//입력단위가 2^31이기 때문에 long long으로 받아야 data손실이 없음!!!
cin >> s >> e;
long long n = 1;
long long dis = e - s - 2;
if (dis <= 0) {
cout << dis + 2 << "\n";
continue;
}
while ((n*n + 3 * n) < dis) {
n++;
}
if ((n*n + 2 * n) <= dis) n *= 2;
else n = n * 2 - 1;
cout << n + 2 << "\n";
}
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 2293번 C++ "동전 1" 풀이 / DP, 배낭 문제, 다이나믹 프로그래밍 (1) | 2024.02.07 |
---|---|
[백준] 15686번 C++ "치킨 배달" 풀이 / 완전 탐색, 조합 / 삼성 sw역량테스트 기출문제 (1) | 2024.02.02 |
[백준] 9251번 C++ "LCS" 풀이 / DP (1) | 2024.01.31 |
[백준] 7569번 C++ "토마토" 풀이 / bfs, 3차원 벡터 (1) | 2024.01.29 |
[백준] 10026번 C++ "적록색약" 풀이 / dfs, 너비 우선 탐색 (0) | 2024.01.27 |