2965번

2965번 - 캥거루 세마리

재귀함수를 이용해서 문제를 풀었다.

그리디 방법으로 보면,

왼쪽 캥거루는 무조건 가장 오른쪽 캥거루보다 한칸 뒤에 위치해야 하고, 

(A,B,C 가 있을 경우 맨 왼쪽 캥거루가 이동한다고 하면 B,A,C가 되어야 하고 이 때 A의 위치는 C-1이 되어야 한다.)

오른쪽 캥거루는 무조건 가장 왼쪽 캥거루보다 한칸 앞에 위치해야 한다.

(A,B,C가 있을 경우 맨 오른쪽 캥거루가 이동한다고 하면 A,C,B 가 되어야 하고, 이때 C의 위치는 A+1이 되어야 한다.)

이런식으로 재귀를 해서, 최대값을 찾으면 된다.

기저 조건은 결국 세 캥거루가 나란히 붙어 있는 경우가 된다.

<정답 코드>

 
#include<iostream>
 
using namespace std;
int ans = 0;
void move(int a, int b, int c, int sum)
{
    if (b == a + 1 && c == b + 1)
    {
        ans = sum > ans ? sum : ans;
        return;
    }
 
    if (c != b + 1)
    {
        move(b, c - 1, c, sum + 1);
    }
    
    if (b != a + 1)
    {
        move(a, a + 1, b, sum + 1);
    }
 
}
 
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    move(a, b, c, 0);
 
    cout << ans << "\n";
    
 
    return 0;
}