I am an potato!.

2 minute read

https://programmers.co.kr/learn/courses/30/lessons/43105

문제 유형 : 동적프로그래밍

image

  • vector 사용 : https://hwan-shell.tistory.com/119 참조
    • vector<자료형>변수명(범위, 초기화할 값)

      백터의 범위 내에서 해당 값으로 초기화 하면서 벡터를 초기화

  • 동적프로그래밍 : https://www.leafcats.com/72 참고
    • 이 사이트에 나오는 방법중 다른 문제에서 가져오는 법을 이용하여 해결하였다. 다른 문제에서 가져오는 법 : 현재 노드의 값을 구하기 위해서 다른 곳(먼저 계산한 작은 문제) 에서 값을 가져와 해결하는 방식 
      // 사이드 초기화
arr[0][0] = triangle[0][0];
for (int i = 1; i < arr.size(); i++)
{
  arr[i][0] = arr[i - 1][0] + triangle[i][0];
  arr[i][i] = arr[i - 1][i - 1] + triangle[i][i];
}
//bottom 방식, 동적프로그래밍 방식
for (int i = 2; i < arr.size(); i++)
{
  for (int j = 1; j < i; j++)
  {
      //부모값은 부모값 + 자식중 큰값
      arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + triangle[i][j];
  }
}

해결방법

  1. 먼저 삼각형의 양 사이드를 초기화해준다. : (예외처리)

  2. 그리고 bottom방식으로 부모결과값 = 부모값 + max(왼쪽 자식, 오른쪽 자식) 이라는 것을 이용해 계산해준후
  3. 삼각형의 가장 마지막부분을 돌아가면서 최대값을 찾아 리턴해준다.

solution

int solution(vector<vector<int>> triangle)
{
    //0으로 초기화된 벡터 생성
    vector<vector<int>> arr(triangle.size(), vector<int>(triangle.size(), 0));

    // 사이드 초기화
    arr[0][0] = triangle[0][0];
    for (int i = 1; i < arr.size(); i++)
    {
        arr[i][0] = arr[i - 1][0] + triangle[i][0];
        arr[i][i] = arr[i - 1][i - 1] + triangle[i][i];
    }
    //bottom 방식, 동적프로그래밍 방식
    for (int i = 2; i < arr.size(); i++)
    {
        for (int j = 1; j < i; j++)
        {
            //부모값은 부모값 = 자식중 큰값
            arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + triangle[i][j];
        }
    }
    int answer = 0;
    for (int i = 0; i < arr.size(); i++)
    {
        // 아래쪽(마지막) 값을 돌아가면서 최대 값을 찾는다.
        answer = max(answer, arr[arr.size() - 1][i]);
    }

    return answer;
}

시행착오

-> 정확성 테스트는 모두 통과했지만, 효율성 테스트에서 떨어졌다. 처음에는 재귀를 이용하여 풀었는데 시간복잡도가 크게 나오는 문제로 for문으로 바꿔서 다시 풀었다.

재귀을 쓴 코드 (효율성 text x)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int dp[500][500] = { 0, };

int dynamicFunc(int h,int i, vector<vector<int>> triangle) {      //h는 높이-1, i는 위치..?
    if (dp[h][i] != 0) {
        return dp[h][i];
    }
    if (i == 0) {

       dp[h][i] = dynamicFunc(h-1,i, triangle)+ triangle[h][i];
    }
    else if (i == h) {
        dp[h][i] = dynamicFunc(h - 1, i-1, triangle) + triangle[h][i];
    }
    else {
        int max = dynamicFunc(h - 1, i-1, triangle) > dynamicFunc(h - 1, i, triangle) ? dp[h - 1][i - 1] : dp[h - 1][i];
        dp[h][i] = max + triangle[h][i];
    }
    return dp[h][i];
}

int solution(vector<vector<int>> triangle) {
    dp[0][0] = triangle[0][0];
    int answer = 0;
    int size = triangle.size();
    for (int j = 0; j < size; j++) {
        answer = max(answer, dynamicFunc(size - 1, j, triangle));
    }
    return answer;
}

You may also enjoy