[C++ 풀이] 11034. 캥거루 세마리2

문제 분석

캥거루의 위치 a,b,c를 입력받고 양 끝의 캥거루만을 움직이면서 사이를 좁혀나가는 문제이다.

이때 a와 b사이의 위치, b와 c사이의 위치를 비교하여 더 긴 쪽으로 캥거루를 옮겨야 움직이는 횟수를 최대로 늘릴 수 있다.

 

알고리즘 설계

움직이는 횟수를 구하는 것이 목표이므로

a와 b, b와 c사이의 더 긴 거리를 구하면 끝이다. 

그 거리내에서만 캥거루들을 움직일 수 있기 때문에 -1을 해준 값을 출력한다.

 

ex)

a:3 b:5 c:9

a나 c캥거루가 캥거루 사이 좌표로 움직여야하므로, a가 b와 c사이로 뛰어간다. 

이때 최대횟수로 만들어야하므로 a는 8로 움직인다. 

이후로는 c가 다시 7로 움직이고, 다시 a가 6으로 움직이고 ... 

이런 식으로 반복이 되므로 

결국은 처음에 주어진 좌표에서 긴 거리를 구하면 끝이다. 

 

시간 복잡도

while문으로 입력받는 값에 따라 달라짐

 

코드

#include <iostream>
using namespace std;
/*
1. 캥거루의 초기 위치 abc를 받는다
2. 각 케이스별로 최대 움직임 횟수를 구한다.
*/

int main() {
    //1
    int a, b, c;

    //2
    while (cin >> a >> b >> c) {
        cout << max(b - a, c - b) - 1 << '\n';
    }
    return 0;
}

 

느낀 점

문제를 손으로 풀어보면서, 캥거루가 뛸 때마다 바뀌는 좌표도 다 입력을 해야하나? 라는 생각이 들어 굉장히 복잡한 알고리즘을 짜야겠다고 생각이 들었다. 

그러나 계산해본 결과 어차피 긴 거리를 선택하면, 그 거리 내에서만 움직이는 게 끝이기 때문에 주어진 거리 중 큰값을 max()함수로 구해서 1을 빼준 거리를 출력하면 된다.