[2965] 캥거루 세마리

왜 이문제가 DP분류로 되어있는지 잘 모르겠다. DP로 생각하다가 막혀서 다르게 풀었다.

#include <cstdio>
using namespace std;
​
int main(){
    int N[3] = {0};
    int cnt=0;
    scanf("%d %d %d",&N[0],&N[1],&N[2]);
    while(true){
        int aSide = N[1]-N[0];
        int bSide = N[2]-N[1];
        if(aSide == 1 && bSide == 1){
            break;
        }else if(aSide > bSide){
            N[2] = N[1];
            N[1] = N[1]-1;
        }else if(aSide <= bSide){
            N[0] = N[1];
            N[1] = N[1]+1;
        }
        cnt++;
    }
    printf("%d\n",cnt);
}

n[0]과 n[1]좌표 사이(aSide), n[1]과 n[2]좌표사이(bSide)의 차잇값을 비교해서 n[1]과 가까이 붙어있는 캥거루를 n[1]옆에 붙인다. 그때 가운데 캥거루와 바깥에 있던 캥거루가 바뀌므로 넘버링을 다시 해줘야한다.