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

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

1011번: Fly me to the Alpha Centauri

코드

#include <iostream>
using namespace std;

int solve(int dis){
	int answer = 0;
	int k = 2;
	if(dis == 1) return -1;
	else if(dis == 2) return 0;
	else{
		dis -= 2;
		while(dis > 0){
			if(dis >= k * 2){
				dis -= k * 2;
				answer += 2;
			}
			else if(dis >= k){
				dis -= k;
				answer += 1;
			}
			else{
				dis -= dis;
				answer += 1;
			}
			k += 1;
		}
	}
	return answer;
}

int main() {
	int t;
	cin >> t;
	
	int x, y;
	
	for(int i=0; i<t; i++){
		cin >> x >> y;
		cout << solve(y - x) + 2 << endl;
	}
}

 

설명

이 문제를 한 세 번째 풀어보는거같은데, 풀 때마다 푸는 방법이 매번 달라지는거같다.

그리고 이번이 가장 빠르게 풀어냈던것 같다.

https://wonsang98.tistory.com/10?category=816114 

1011번: Fly me to the Alpha Centauri(백준 C++)

저번에 이렇게 풀었다고 포스팅 해놨는데

지금 내가 다시 봤는데 무슨 말을 하는건지 한 서너번 정독하고 이해했다.

다시 보니까 풀이 방법은 지금이랑 같은데, 코드가 조금? 다른 것 같다.

접근한 방법에 대해 간략하게 이야기하고 넘어가자면

1) Distance를 입력받는다.

x, y 값을 받게 되는데, y - x 가 Distance가 된다.

 

2) Distance 가 2 이하인경우

우선 문제를 잘 읽어보면, 시작할때와 도착할때는 무조건 1의 거리만 이동한다고 되어있다.

즉, 거리가 어떻게 되든 2만큼은 빼고 봐야한다는 건데 그렇기 때문에

Distance가 1 , 2 인 경우에는 결과값으로 1, 2를 출력하게 해준다.

Distance가 2를 넘어가는 순간부터는 다음 방법으로 접근해보자.

 

3) Distance 가 3 이상인경우

앞서 말했듯이, 시작과 끝은 무조건 1이므로 우선, Distance에서 2를 빼준다.

좀 더 쉬운 이해를 돕기 위해 예시로 Distance가 10이라고 가정해보자.

그리고 10에서 처음과 끝을 빼서 생각할 거리는 8이 되었다.

그리고 양 끝에서 최대 이동거리는 각각 2이다.

각각 2만큼 움직인다고 해도 남은 거리에 문제가 있는가?

없다. 그렇다면 2만큼 이동해주자.

이제 남은 거리는 4.

그리고 양 끝에서 최대한 이동 가능한 거리는 '3' 이다.

3만큼 이동할 수 있는가?

한 쪽은 가능하지만, 한 쪽에서 3만큼 이동하면 반대편은 거리가 1밖에 남지않기때문에 불가.

그렇다면 한 쪽만 3만큼 이동해준다.

그러면 이동해야할 거리가 1만큼이되고

1 -> 2 -> 3 -> 1 -> 2 -> 1

이렇게 이동한것처럼 보인다

그런데, 3 다음에 1만큼 움직이는건 안되지 않나요? 라고 생각할수있다.

이건 순서의 문제이다.

단순히 이렇게 바꿔주기만해도 6번의 움직임으로 도달했다는걸 알 수있다.

 

즉, 우선 양 끝에서 1을 빼주고

양 끝에서 2부터 시작해서 차츰 높은 숫자만큼 양 끝, 혹은 한 쪽에서 빼주면 된다.