[백준] 2965 캥거루 세마리

2965번: 캥거루 세마리

 

www.acmicpc.net

풀이

캥거루 간의 간격을 최대한 길게 유지하면 된다.
예를 들어 캥거루의 위치가 3 5 10 이라면 첫 번째 간격은 2이고 두 번째 간격은 5이다. 따라서 3에 있던 캥거루가 5와 10 사이에 들어가면 되는데, 이 때 그 다음에 다시 점프할 때를 생각해서 계속해서 긴 간격을 유지해야한다. 따라서 5와 10 사이에서 6 또는 9에 점프하게 된다. 5 6 10이라고 하면 그 다음엔 5 캥거루가 7로 점프한다. 이런 방식으로 반복하면 최대 횟수가 된다는 것을 알 수 있다. 따라서 맨 처음 캥거루 사이의 간격의 최대값 - 1이 정답이 된다.

코드

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

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