백준 1011 Fly me to the Alpha Centauri

Fly me to the Alpha Centauri

문제 링크

1011번: Fly me to the Alpha Centauri

이 문제는 1년전에 풀어봤던 문제인데 이 때도 정말 고민하고 생각하면서 겨우 풀었던 것으로 기억한다. 근데 이번에는 풀다가 도저히 생각이 안나서 작년에 내가 푼 문제를 보았다. 쓰레기 짜식..... 할튼 알고보니? 쉬운 문제였다. 

 

이 문제의 경우의 수를 잘 생각해보면 아래와 같이 나올 수 있다. 

거리	방법
3	1 1 1
4	1 2 1
5	1 2 1 1
8	1 2 1 2 1

 

잘보면 좌우대칭이 발생하는 것을 확인할 수 있다. 그래서 나의 경우에는 시작점은 더해주고 최종점은 마이너스 해주는 방식으로 대칭적으로 만들어주었다. 그 후 시작점과 종료점이 교차된다면 그대로 count한 것을 출력. 또는 움직일 수 있는 거리랑 남은 거리가 같거나 커질 경우 +1을 해주면서 종료할 수 있다.

 

#include <cstdio>
#include <vector>
#define ll long long

using namespace std;

vector<int> movePoint;

int main(){
	ll T, x, y;
	scanf("%lld", &T);

	for(int i = 0; i < T; i++){
		scanf("%lld %lld", &x, &y);
		ll move = 1, count = 0;
		ll start = x, desination = y;

		while(1){
			ll diff = desination - start;
			if(start >= desination){	
				printf("%lld\n", count);
				break;
			}else if(move >= diff){
				printf("%lld\n", count+1);
				break;
			}

			start+= move, desination -= move;
			count += 2, move += 1;
		}
	}
}