2965)캥거루 세 마리

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

수직선 위에 서로 다른 정수점 세 개가 주어진다.

가장 바깥쪽에 있는 정수점 하나는 다른 두 정수점 사이로 뛰어들 수 있지만 다른 정수점과 겹칠 수는 없다.

이 규칙으로 정수점 사이를 뛰어들 때 최대한 많이 뛰는 횟수를 찾는 문제다.

예를들어 정수점이 1,4,9라고 하자.

정수점은 위 그림과 같다.

여기서 1이 4~9 사이로 뛰어들든가 9가 1~4 사이로 뛰어드는 방법이 있다.

딱보기에도 1이 4~9사이로 뛰어드는 방법이 4~9의 간격이 크기 때문에 많이 뛸 수 있어 보인다.

여기서 가능하면 정수점 사이의 간격을 크게만들어주는 방향으로 뛰어드는 것이 좋다는 것을 알 수 있다. 

정수점 1이 4옆으로 뛰어들었다. 애매모호하게 6이나 7로 뛰어든게 아니라 5로뛰어들어 9와 간격을 크게 만들었다.

위 그림처럼 뛰는 방법이 최대 횟수로 뛰는 방법이다.

따라서 두 점 사이의 간격 중 더 큰 것에서 1을 빼준 결과가 구하고자 하는 최댓값이다.

#include<stdio.h>
#define MAX(A,B) (A>B)?A:B
 
void insertionSort(int *A, int n) {
    int temp;
    int t;
 
    for (int i = 1; i < n; i++) {
        temp = A[i];
        t = i - 1;
        while (t >= 0 && A[t] > temp) {
            A[t+1] = A[t];
            t--;
        }
        A[t+1] = temp;
    }
}
 
int main() {
    int maxDifference = 0;
    int num[3];
 
    for (int i = 0; i < 3;i++) {
        scanf("%d",&num[i]);
    }
    insertionSort(num, 3);
 
    maxDifference = MAX(maxDifference, num[1] - num[0]);
    maxDifference = MAX(maxDifference, num[2] - num[1]);
 
    printf("%d\n",maxDifference-1);
 
    return 0;
}