[프로그래머스] level 3 - 정수 삼각형 (C++)

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

문제 풀이

dp 유형의 문제. 처음에 dp배열을 vector로 선언했다가 계속 시간초과가 났는데 2차원 배열로 바꿨더니 간단하게 통과했다.

vector는 인덱싱을 지원하지 않기 때문에 각 원소에 접근할때 포인터를 이용(시간이 일정하지 않음)하므로 배열에서 인덱스로 접근(인덱스마다 시간 일정)하는 것 보다 시간이 느리다고 한다. 참고하자! (물론 이중연결리스트보단 훨씬 빠르다)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int dp[500][500];
vector<vector<int>> nums;
int getDP(int row, int col)
{    
    if (row == nums.size() || dp[row][col] != 0) return dp[row][col];
    
    dp[row][col] = nums[row][col] + max(getDP(row+1, col), getDP(row+1, col+1));
    return dp[row][col];    
}
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    nums = triangle;
    
    for (int i=0; i<n; i++)
    {
        dp[n-1][i] = triangle[n-1][i];
    }
    
    answer = getDP(0,0);   
    return answer;
}

 

+) vector와 array 차이점 참고 블로그

https://sueaty.tistory.com/59

[C++] Array 와 Vector 한 방에 비교하기