[백준OJ] 11034번 캥거루 세마리2

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

11034번: 캥거루 세마리2

---

 

-풀이-

세마리의 캥거루의 위치를 A,B,C라고 해보겠다.

양쪽 캥거루중 한마리가 나머지 두 캥거루의 사이로 가야된다. 이때, A-B사이의 거리와, B-C사이의 거리를 구한뒤, 더 작은쪽거리에 있는 캥거루를, 긴 거리에있는 캥거루 사이에 둔다. 왜냐면, 점프횟수를 최대로 해야하므로, 기회가 더 많이 생길 수 있도록 작은쪽의 캥거루를 긴 캥거루 사이로 넣어야된다.

그럼 거리가 긴 캥거루 사이 어디에 놔야할까? 답은 간단하다.점프를 최대로 하려면 캥거루 두마리중 하나와 딱 붙여놓으면 된다.

 

예를들어 캥거루의 위치가 3 / 5 / 9에 있다고 하자.

왼쪽 거리는 2, 오른쪽 거리는 4이므로, 1번째 캥거루를 2~3 사이에 점프시킬것이다. 이때 2번위치에 있는 캥거루에 붙이면 5 / 6 / 9 가 된다.

다음으로, 왼쪽거리는 1이되고, 오른쪽은 3이되므로, 1번째 위치의 캥거루를 2~3 사이에 점프시킬것이다. 이때도 2번 위치에 있는 캥거루 옆에 붙이면 6 / 7 / 9 가 된다.

위와 마찬가지로 다음 단계를 진행하면 7 / 8 / 9가 되면서 점프의 횟수는 최대가 된다.

 

-시간복잡도-

O(1)

 

-코드-

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<string> v;
int main() {
	int a, b, c;
	while (cin >> a >> b >> c) {
		int cnt = 0;
		while (true) {
			if (b - a == 1 && c - b == 1) break;
			int lgap = (b - a);
			int rgap = (c - b);
			if (lgap < rgap) {
				a = b;
				b = b + 1;
			}
			else {
				c = b;
				b = b - 1;
			}
			cnt++;
		}
		cout << cnt<<"\n";
	}
	return 0;
}