15645 내려가기

 

문제 봤을 때 딱 봐도 디피라 디피 사용했긴 했는데 틀려서 계속 해맸었다.

 

정의는 위의 사진처럼 적당히 이렇게 하면 굴러가겠지 싶어서 이렇게 짰는데 역시나 틀렸고 원인을 못 찾았다ㅋㅋ

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 1000000

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int min_cache[100005][3];
int max_cache[100005][3];
int v[100005][3];
int n;

int     func_min(int i, int j, int sum)
{
    if (i == n + 1)
        return sum;

    int& ref = min_cache[i][j];
    if (ref != -1)
        return ref;

    int a = MAXV, b = MAXV, c = MAXV;
    if (j == 1 || j == 0)
        a = func_min(i+1, 0, sum + v[i+1][0]);
    b = func_min(i + 1, 1, sum + v[i + 1][1]);
    if (j == 1 || j == 2)
        c = func_min(i + 1, 2, sum + v[i + 1][2]);

    return ref = min({ a, b, c });
}

int     func_max(int i, int j, int sum)
{
    if (i == n + 1)
        return sum;

    printf("%d %d %d\n", i, j, sum);

    int& ref = max_cache[i][j];
    if (ref != -1)
        return ref;

    int a = 0, b = 0, c = 0;
    if (j == 1 || j == 0)
        a = func_max(i + 1, 0, sum + v[i + 1][0]);
    b = func_max(i + 1, 1, sum + v[i + 1][1]);
    if (j == 1 || j == 2)
        c = func_max(i + 1, 2, sum + v[i + 1][2]);

    return ref = max({ a, b, c });
}



int     main()
{
    memset(min_cache, -1, sizeof(min_cache));
    memset(max_cache, -1, sizeof(max_cache));

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d\n", &v[i][0], &v[i][1], &v[i][2]);

    func_min(0, 1, 0);
    func_max(0, 1, 0);

    printf("%d %d\n", max_cache[0][1], min_cache[0][1]);

    for (int i = 0; i <= n; i++)
        printf("%d %d %d\n", max_cache[i][0], max_cache[i][1], max_cache[i][2]);
    
    return 0;
}

 

 

 

그래서 도움 받아서 풀었음

 

문제 풀면서 살짝 느끼긴 했는데 이런 재귀는 시작점과 관련해서 생각하는 게 중요한 것 같다. 

 

크기가 1일 때 어떻게 동작하는지 정의 내리고 그 다음으로 꼬리 무는 부분 (반복되는 부분)을 잘 설정하면 되는 듯?

 

고등학교 때 배운 점화식 같다.

 

그 때 생각해보면 n = 1일 때 정의내리고 그 다음으로 n, n+1일 때 생각하잖어

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 1000000

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int min_cache[100005][3];
int max_cache[100005][3];
int v[100005][3];
int n;

int     func_min(int i, int j)
{
    if (i == n + 1)
        return 0;

    int& ref = min_cache[i][j];
    if (ref != -1)
        return ref;

    int a = MAXV, b = MAXV, c = MAXV;
    if (j == 1 || j == 0)
        a = func_min(i+1, 0);
    b = func_min(i + 1, 1);
    if (j == 1 || j == 2)
        c = func_min(i + 1, 2);

    return ref = v[i][j] + min({ a, b, c });
}

int     func_max(int i, int j)
{
    if (i == n + 1)
        return 0;

    int& ref = max_cache[i][j];
    if (ref != -1)
        return ref;

    int a = 0, b = 0, c = 0;
    if (j == 1 || j == 0)
        a = func_max(i + 1, 0);
    b = func_max(i + 1, 1);
    if (j == 1 || j == 2)
        c = func_max(i + 1, 2);

    return ref = v[i][j] + max({ a, b, c });
}



int     main()
{
    memset(min_cache, -1, sizeof(min_cache));
    memset(max_cache, -1, sizeof(max_cache));

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d\n", &v[i][0], &v[i][1], &v[i][2]);

    func_min(0, 1);
    func_max(0, 1);

    printf("%d %d\n", max_cache[0][1], min_cache[0][1]);
    
    return 0;
}