1011번: Fly me to the Alpha Centauri
문제
https://www.acmicpc.net/problem/1011
풀이
문제에서 출발과 도착하기 바로 직전의 이동거리는 1광년만 이동가능하다. 가장 먼저 작동 횟수의 최솟값이기 때문에 이동 거리는 점점 커지다가 줄어야 한다고 생각했다. 출발점과 도착점에서 거리가 1씩 커지면서 출발한다고 생각했고 두 지점 간 거리가 양수인 동안 먼저 (두 지점 간 거리)에서 (이동 거리 × 2) 씩 빼주고 (정답 카운트)를 2씩 올려줬다. 두 점이 아직 만나지 않았다면 (이동 거리)를 1 증가시켰고 만약 두 점이 만나거나 지나치게 되면 (두 지점 간 거리)가 0이 될 때까지 반복문을 돌려주었다. 만약 (두 지점 간 거리)가 음수라면 지나치게 된 것이므로 (이동 거리)만큼 (두 지점 간 거리)를 늘려주고 (정답 카운트)를 1 뺐다. 그리고 (이동 거리)만큼 가면 지나치게 되는 것이므로 (이동 거리)를 1 줄였다. 만약 (두 지점 간 거리)가 양수라면 아직 만나지 못한 것이므로 (이동 거리)만큼 (두 지점 간 거리)를 줄이고 (정답 카운트)를 1 더했다. 그리고 아직 거리가 더 남았을 수 있으니 (이동 거리)를 1 늘려주었다.
예시
예시로 x = 0, y = 10인 경우를 들어보자.
여기서 (이동 거리)란 이동 후 1 늘린 상태로 즉, (다음 이동 거리)다.
처음엔 (두 지점 간 거리) = 10, (이동 거리) = 1, (기계 작동 횟수) = 0 이다.
첫 이동 후 (두 지점 간 거리) = 8, (이동 거리) = 2, (기계 작동 횟수) = 2
두 번째 이동 후 (두 지점 간 거리) = 4, (이동 거리) = 3, (기계 작동 횟수) = 4
세 번째 이동 후 (두 지점 간 거리) = -2, (이동 거리) = 3, (기계 작동 횟수) = 6이 되어 (두 지점 간 거리)가 0보다 작아졌다. (반복문 진입)
(두 지점 간 거리)가 음수이므로 한 점이 이전에 이동한 (3)만큼 돌아가고 (기계 작동 횟수)를 1번 감소시킨다. 그리고 (이동 거리)를 1 감소시킨다.
그럼 (두 지점 간 거리) = 1, (이동 거리) = 2, (기계 작동 횟수) = 5 이 된다.
(두 지점 간 거리)가 양수이므로 한 점이 (이동 거리 = 2)만큼 이동하고 (기계 작동 횟수)를 1 증가시킨다. 그리고 (이동 거리)를 1 증가시킨다.
그럼 (두 지점 간 거리) = -1, (이동 거리) = 3, (기계 작동 횟수) = 6
다시 (두 지점 간 거리)가 음수이므로 한 점이 이전 이동 거리(2)만큼 이동했을 때 지나치게 되니 (이동 거리 = 3)만큼 돌아가고 (기계 작동 횟수)를 1번 감소시킨다. 그리고 (이동 거리)를 1 감소시킨다.
그럼 (두 지점 간 거리) = 2, (이동 거리) = 2, (기계 작동 횟수) = 5
다음으로 (두 지점 간 거리)가 양수이므로 한 점이 (이동 거리 = 2)만큼 이동하고 (기계 작동 횟수)를 1 증가시킨다. 그리고 (이동 거리)를 1 증가시킨다.
그럼 (두 지점 간 거리) = 0, (이동 거리) = 3, (기계 작동 횟수) = 6
(두 지점 간 거리)가 0이 되었으므로 모든 반복문을 탈출한다.
정답은 (기계 작동 횟수)인 6이 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int t;
cin >> t;
while (t--) {
int x, y, ans = 0;
cin >> x >> y;
int gap = y - x, k = 1;
while (gap) {
gap -= 2 * k;
ans += 2;
if (gap <= k) {
while (gap != 0) {
if (gap < 0) {
gap += k;
ans--;
k--;
} else if (gap > 0) {
gap -= k;
ans++;
k++;
}
}
}
k++;
}
cout << ans << '\n';
}
return 0;
}
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 1018 체스판 다시 칠하기 (0) | 2023.02.07 |
---|---|
[백준 / BOJ] C++ 1012 유기농 배추 (0) | 2023.02.07 |
[백준 / BOJ] C++ 1010 다리 놓기 (0) | 2023.02.06 |
[백준 / BOJ] C++ 17087 숨바꼭질 6 (0) | 2023.02.06 |
[백준 / BOJ] C++ 1009 분산처리 (0) | 2023.02.06 |