1011: Fly me to the Alpha Centauri

• toc {:toc}

문제 확인하기

풀이

처음 시작할 때와 끝날 때 1로 시작하고 1로 끝나야 한다는 점을 예외사항으로 생각해두고 풀이한다.

이동할 수 있는 방식이 n-1, n, n+1로 사용하는 방식이기 때문에 어느 정도 대칭적으로 계산해야 한다고 생각했다.

예를 들어 x, y가 각각 0, 5라고 하면 5를 이동해야 한다. 시작, 도착 1광년 2번 생각하면 3이 남고, 내가 선택할 수 있는 이동 방식이 1광년 이동 혹은 2광년 이동이다. 2광년 2번은 사용할 수 없기 때문에 2, 1을 사용해야 한다.

즉, n광년x2 보다 남은 거리가 길다면 대칭적으로 계산해주면 되고, n광년x2 보다 남은 거리가 짧거나 같다면 n광년을 1번만 적용해준다. 같을 경우에는 n+1광년 1번으로 처리할 수 있는 경우(n=1 남은 거리=2)와 처리할 수 없는 경우(n=3, 남은 거리=6)가 있어 처리해준다.

처음에 생각해두었던 예외사항까지 시작 단계에 적용해준다.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	int T, x, y; 
	long long num, res = 0;
 
	cin >> T;
 
	for(int i = 0; i < T; i++){
		num = 1;
		res = 0;
		cin >> x >> y;
		long long diff = y - x;
		if(diff == 2){
			cout << 2 << '\n';
			continue;
		}
		while(true){
			if(num * 2 < diff){
				diff = diff - num * 2;
				res += 2;
				num++;
			}
			else if(num * 2 == diff){
				if (num+1 < diff) res += 2;
				else res++;
				break;
			}
			else {
				diff = diff - num;
				res++;
			}
			if(diff <= 0) break;
		}
		cout << res << '\n';
	}
 
	return 0;
}

풀이를 반례를 찾아가며 끼워맞추기로 해서 이렇게 푸는 것이 옳은 것인가 생각이 들어 다른 풀이를 찾아봤더니 표를 그려 규칙성을 찾는 방식으로 많이 풀이했다. 체크해두고 다시 풀어봐야겠다.