99클럽 코테스터디 21일차 TIL 정수 삼각형

정수삼각형

프로그래머스 level 3 DP

문제링크

문제설명

문제풀이

DP를 푸는 것이 익숙하지 않아서, BruteForce 방식으로 우선적으로 풀이하고, DP로 바꾸는 작업을 거쳐 풀이했다.

int brute (int cur, int prev, int lim, vector<vector<int>>& tri) {
    if (cur == lim) {
        return 0;
    }
    if (memo[cur][prev] != -1) {
        return memo[cur][prev];
    }

    int tmp1 = brute(cur+1, prev, lim, tri);
    int tmp2 = brute(cur+1, prev+1, lim, tri);

    memo[cur][prev] = tri[cur][prev] + max(tmp1, tmp2);

    return memo[cur][prev];
}

memo 라는 2차원 배열을 -1로 초기화 해주고 값을 저장해 나가는 방식으로 풀이했다.

 

하지만 해당 문제는 하향식 접근으로 풀면, 문제 자체는 풀리지만 효율성테스트에서 실패하는 문제였다.

 

상향식 접근은 아예 감이 안와서 풀이한 코드를 gpt 한테 주고 바꿔달라고 하니까 야무지게 바꿔줘서 그걸로 통과했다.

통과한 코드

#include <string>
#include <vector>
#define MAXL 501

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;

    for (int i=triangle.size()-2; i>=0; i--) {
        for (int j=0; j<=i; ++j) {
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }
    return triangle[0][0];
}

회고

DP 문제는 항상 어렵게 느껴지고 풀기싫어서 기피해왔었는데, 오늘 잘 풀려서 기분 좋았었다.

SSAFY 다니면서 DP 를 어떻게 풀어야 할지 친구한테 물어본 적 있었는데, 그 친구는 처음에 공부할 때 일단 완전탐색으로 풀고 그것을 최적화 하는 방향으로 DP를 공부했다고 해서 적용해봤는데, 잘 되서 신기했다.

답 안보고 푼 최초 dp 문제가 될 수 있었는데 아쉽다.

답을 볼때마다 드는 생각인데, dp 는 유독 답이 내 코드보다 너무 간결하고 알아보기 쉬운 것 같다. 점화식 세우는게 아직 익숙하지 않은듯.