ALGOSPOT TRIANGLEPATH

2020.02.17

TRIANGLEPATH

풀이

• 행을 한칸씩 이동할 때, 아래와 오른쪽 대각선 아래 두가지 경우의 수가 있다.
• 재귀함수를 이용해서 마지막 행에 도착하는 순간 그때의 최대 거리를 리턴하는 getResult 함수를 만들었다.
• 처음에 메모이제이션을 마지막에 도달했을 때 최댓 거리를 DP 행렬에 기록하려고 시도했었다.
• 우연히 정답이 나왔으나 이는 같은 결과가 나올 수 없었다. 경로가 달라질 때마다 마지막에 도달하는 거리는 달라진다.
• 같은 지점에 대해 같은 결과가 나오는 것에 대해 메모이제이션을 활용해야 하는데 잘못된 알고리즘을 구상한 것이다.

잘못된 메모이제이션 활용

//! 2020.02.17
// TODO AS_TRIANGLEPATH.cpp
// Dynamic Programming
#include<cstdio>
using namespace std;

const int MAX = 105;
int DP[MAX][MAX];
int inMap[MAX][MAX];
int C, N;

void resetMap(int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            DP[i][j] = -1;
            inMap[i][j] = 0;
        }
    }
}

int getResult(int y,int x,int dist) {
    int& ret = DP[y][x];
    if (ret != -1) return ret;
    if (y>=N-1) {
        return ret = dist+inMap[y][x];
    }
    else {
        dist += inMap[y][x];
        int tmpMax1 = -1;
        int tmpMax2 = -1;
        if (x <= y) tmpMax1 = getResult(y+1, x + 1, dist);
        tmpMax2 = getResult(y+1, x, dist);
        return ret = tmpMax1 > tmpMax2 ? tmpMax1 : tmpMax2;
    }
}

int main() {
    scanf("%d", &C);
    resetMap(MAX, MAX);
    for (int c = 0; c < C; c++) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i+1; j++) {
                scanf("%d", &inMap[i][j]);
            }
        }
        printf("%d\n", getResult(0,0,0));
        resetMap(N, N);
    }

    return 0;
}

수정

해당 지점 이후로 가장 큰 경로의 거리를 기록하도록 메모이제이션 활용을 바꿨다.

이렇게 하게 되면 내 다음 경로의 두가지 경우 중 큰 경우를 구해서 기록하게 되는데, 이는 매번 같은 결과일 수 밖에 없었고 문제를 해결할 수 있었다.

올바른 메모이제이션 활용

//! 2020.02.17
// TODO AS_TRIANGLEPATH.cpp
// Dynamic Programming
#include<cstdio>
using namespace std;

const int MAX = 105;
int DP[MAX][MAX];
int inMap[MAX][MAX];
int C, N;

void resetMap(int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            DP[i][j] = -1;
            inMap[i][j] = 0;
        }
    }
}

int getResult(int y,int x) {
    int& ret = DP[y][x];
    if (ret != -1) return ret;
    if (y>=N-1) {
        return ret = inMap[y][x];
    }
    else {
        int tmpMax1 = inMap[y][x];
        int tmpMax2 = inMap[y][x];
        if (x <= y) tmpMax1 += getResult(y+1, x + 1);
        tmpMax2 += getResult(y+1, x);
        return ret = tmpMax1 > tmpMax2 ? tmpMax1 : tmpMax2;
    }
}

int main() {
    scanf("%d", &C);
    resetMap(MAX, MAX);
    for (int c = 0; c < C; c++) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i+1; j++) {
                scanf("%d", &inMap[i][j]);
            }
        }
        printf("%d\n", getResult(0,0));
        resetMap(N, N);
    }

    return 0;
}