백준) 2965 캥거루 세마리

캥거루 세마리

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

캥거루 세 마리가 직선 위에 존재하고, 양 끝의 캥거루가 나머지 두 마리의 가운데로 점프해서 끼어들 수 있다.

단, 같은 지점에 두마리 이상 존재할 수 없을 때, 점프를 최대한 어람나 할 수 있을까?

세 마리가 동일한 지점에 있다면 항상 같은 결과가 나온다는 생각으로, dp를 시도해 볼 수 있다.

점프 이후 전에 계산했던 상황이 나오면 재활용 할 수 있는 것이다.

각 상황은 세 마리의 위치로 구분되므로, dp[100][100][100]으로 조질 수 있다. 최악의 경우 백만번의 연산을 수행한다.

재귀적으로 왼쪽, 오른쪽 캥거루가 움직일 경우에 최대 점프수를 알아내서, 그 중 최대값에 1을 더해주면 답이다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
int a, b, c;
int dp[100][100][100];
 
 
int func(int a, int b, int c) {
    if (a + 1 == b && b + 1 == c)
        return 0;
 
    int& ref = dp[a][b][c];
    if (ref != -1)
        return ref;
 
    int pp = 0;
    for (int p = a + 1; p < b; ++p) {
        int t = func(a, p, b);
        if (pp < t)
            pp = t;
    }
 
    int qq = 0;
    for (int q = b + 1; q < c; ++q) {
        int t = func(b, q, c);
        if (qq < t)
            qq = t;
    }
 
    return ref = max(pp, qq) + 1;
}
 
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d %d %d", &a, &b, &c);
    printf("%d", func(a, b, c));
 
    return 0;
}