[백준 C++] 1011 Fly me to the Alpha Centauri

한번 꼬여서 계속 덮어뒀던 문제,,, 새롭게 시작하니 생각보다 되게 간단하게 풀렸다,,,!

 

Problem

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

1011번: Fly me to the Alpha Centauri

 

문제를 요약하자면, 한번 작동할 때 앞서 이동한 거리가 k광년이면 k-1, k, k+1광년만큼을 이동할 수 있는 우주선이 있다. 해당 우주선을 이용해 이동을 할 것이다. 예를 들어 우주선을 처음 작동할 때는 무조건 1광년만큼을 이동할 수 있으며 도착할때 직전 이동거리가 1광년이어야한다. 정확히 도착하기 위한 최소 작동 횟수를 구하는 문제이다.

→ 한 번 이동할 떄 최대 이동거리만큼 이동하되, 정확히 도착지점에서 멈출 수 있도록 적절하게 속도를 줄여야한다.

 

 

 

 

Solution

 

우선 두 지점 사이의 거리 별 최적 방법을 정리해보자.

두 지점 사이의 거리 (dist)	최적 방법
1	1
2	1    1
3	1    1    1
4	1    2    1
5	1    2    1    1
6	1    2    2    1
7	1    1    2    2    1
8	1    2    2    2    1
9	1    2    3    2    1
12	1    2    3    3    2    1
16	1    2    3    4    3    2    1

이렇게 보면 최대로 대칭이 맞춰질 때 이동 횟수가 증가한다.

그럼 이제 대칭이 몇번째마다 맞춰지는지가 관건이다.

→ 이동 횟수가 증가하는 경계에 있는 dist들을 보면, 사이의 거리가 2 두번, 3 두번, 4 두번, 이런식으로 증가한다. 그 이유는 대칭이 맟춰지기 위해 사이에 2가 두 개 들어오고 3이 들어오는 식이 되어야하기 때문.

 

이제 더욱 보기 편하도록 표를 다르게 정리해보자. 이 표를 정리할 때엔 위에서 규칙을 어느정도 알았으므로 일일히 최적 방법을 구하지 않아도 쉽게 쓸 수 있다.

이동 횟수	이동 거리 (dist)
1회 이동	1
2회 이동	2
3회 이동	3, 4
4회 이동	5, 6
5회 이동	7, 8, 9
6회 이동	10, 11, 12
7회 이동	13, 14, 15, 16
8회 이동	17, 18, 19, 20
9회 이동	21, 22, 23, 24, 25

 

이제 다시 문제로 돌아가자. x 지점과 y 지점이 주어졌지만 우리가 결국 필요한 값은 두 지점 사이의 거리인 dist ( y-x ) 이다. 바로 위 표를 계속 써나갈 때, 주어진 dist에 해당하는 이동 횟수를 구하면 된다.

 

 이제 구현해보자.

나는 while문을 통해 한 루프가 위 표의 한 행이 된다고 생각하며 풀이했다. 즉 무한 while문을 돌리는데 한 사이클에 이동 횟수(ans)가 1씩 증가할 것이다. 

ll solve(ll dist){
	ans = 0;

	while(1){
		ans++;
	}
}

 

우선 tmp 변수를 선언하고 해당 tmp 변수가 위 표 이동거리들의 최솟값 (1,2,3,5,7,10,13,17...)이 되도록 하면서 해당 값이 문제에서 주어진 거리(dist)보다 크다면 이 전 이동거리를 출력하도록 했다.

ll solve(ll dist){
	tmp = 1;
	ans = 0;

	while(1){
		ans++;
		tmp = 다음 행 이동 거리의 최소;

		if(dist<tmp) return ans;
	}
}

 

이제 tmp변수를 어떻게 구할것인가. 맨 처음에 파악한 것처럼 tmp의 증가폭은 1씩 두번, 2씩 두번, 3씩 두번... 이렇게 증가할 것이다. 이 때 1, 2, 3을 i라고 선언하자. 그럼 i를 두 번에 한 번씩 증가시켜야한다. ans는 매 사이클에 한 번씩 증가하므로 해당 값의 짝/홀 여부를 통해 i의 증가여부를 판단할 수 있다.

ll solve(ll dist){
	tmp = 1;
	i = 1;
	ans = 0;

	while(1){
		ans++;
		tmp += i;
		if(ans%2==0) i++;

		if(dist<tmp) return ans;
	}
}

 

 

 

 

 

Answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll tcase, x, y, dist;
ll ans, tmp, i;

ll solve(ll dist){
	tmp = 1;
	i = 1;
	ans = 0;

	while(1){
		ans++;
		tmp += i;
		if(ans%2==0) i++;

		if(dist<tmp) return ans;
	}
}

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> tcase;

	while (tcase--) {
		cin >> x >> y;
		dist = y - x;

		cout << solve(dist) << '\n';
	}

}