[백준-1011]Fly me to the centauri(C++)

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

1011번: Fly me to the Alpha Centauri

출발지에서 도착지까지 이동하는데, 처음, 마지막 속도는 1이고
속도를 k-1,k,k+1로 설정하여 이동할 수 있습니다.
이 때 도착지까지 최소한으로 이동하는 횟수를 구하는 문제입니다.

 

 

예) 출발지 = 1, 도착지 = 5

1, 2, 1 이렇게 이동하면 최소한으로 이동한 것이 됩니다.

횟수는 3이므로 답은 3입니다.

 

 

처음에 문제 풀 때, 시간 초과가 계속 났습니다.

벡터 쌍으로 출발지, 도착지 입력을 받고,

도착지 보다 현재위치+지금속도+1이 더 크면 속도를 줄이고

도착지보다 더 작으면 그만큼 이동하려고 했습니다.

근데 계속 시간초과가 떠서..

좀 더 규칙을 찾을 필요가 있었습니다!

 

 

 

문제 해결방법

이동 횟수	최댓값으로 이동하는 방법	이동 거리
1	1	1
2	1+1	2
3	1+2+1	4
4	1+2+2+1	6
5	1+2+3+2+1	9
6	1+2+3+3+2+1	12
7	1+2+3+4+3+2+1	16

이동 횟수 별 최대 방법은 위처럼 됩니다.

위는 최댓값이고, 

4번이동으로는 안되고 5번이동으로만 되는 경우는

12321, 12221, 12121 .. 등이 있습니다.

하지만 이 경우는 4와 5사이에 속하지만 4는 안되므로, 5번 이동 해야 하는 경우입니다.

그러므로 답은 5가 됩니다.

 

문제에서는 정확한 이동방법을 구하는것이 아닌, 이동 횟수만을 구하면 되므로

1+2+2+1보다 크면서 1+2+3+2+1보다 작은 경우, 더 큰 이동 횟수가 답이 됩니다.

 

 

예) 가야하는 거리가 11 인경우

이동값(k)	남은거리	이동 횟수(답)
1	10	1
1	9	2
2	7	3
2	5	4
3	2	5
3	-1	6

 

답은 5->6에서 음수가 되므로, 6번 이동으로 갈 수 있습니다.

이동 과정을 적어본다면 123221 이 되겠습니다.

 

이동 거리에서 k = 1부터 시작하여 k를 두번씩 빼준 뒤, k를 1증가시키는 것을 

반복하다가, 남은 거리가 0또는 음수가 됬을 때 k를 뺀 횟수를 출력하면 답이 됩니다.

 

소스 코드(C++)

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, ans, length, k; //테스트 케이스 수, 답, 남은 길이, 이동 길이
	bool even; //k를 더하는 횟수의 짝/홀 수 판별

	vector <int> v;
	
	cin >> N;

	for (int i = 0; i < N; i++) { //입력
		int a, b;
		cin >> a;
		cin >> b;
		v.push_back(b - a); //거리로 저장
	}

	for (int i = 0; i < N; i++) {

		ans = 0;
		length = v[i]; //남은 길이 = 거리
		even = false; //초기값 = 홀수번
		k = 1; 

			while (length > 0) { //길이가 0보다 큰 동안 진행
				length -= k; //k만큼 길이를 빼주고 답++
				ans += 1;

				if (even) { //k를 두번 더했으면, 1늘려줌
					k = k + 1;
					even = false;
				}
				else { //k 한번 더했음
					even = true;
				}
			}
		cout << ans << endl;
	}
}

코드 설명

1. 입력받은 값을 도착지-출발지로 하여 거리로 저장

2. 남은 길이가 양수이면 k값 만큼 빼주고 이동횟수(ans)++

3. k를 두번 다 더했으면 k값을 1 증가 시켜줌

4. k값을 한번 더 한거면 even을 true로 바꿔줌 - 다음번에 더하는게 두번째

5. length가 음수가 됐을 때 반복문을 빠져나오고, 답 출력