[프로그래머스] 정수 삼각형

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

코딩테스트 연습 - 정수 삼각형

---

풀이)

일반적인 dp문제이다. 삼각형을 2차원 배열로 설정하기 까다로우니 좌측으로 몰았다

v

vv

vvv

vvvv

vvvvv

 

이런식으로 좌측으로 몰아서 인덱싱을 하니 간편했다.

 

dp[i][j]= i번째 높이(위에서 부터 0,1,2,....)에서 j번째 위치까지 오는데 걸리는 최대 합이다

따라서 dp[i][j]는 바로 위의 dp[i-1][j]과 dp[i-1][j-1]두개중 큰것과 자기 자신의 값을 더해주면 되는데

각 줄의 처음은 dp[i-1][j]만 고려해주면되고, 마지막은 dp[i-1][j-1] 만 고려해주면 되는 문제이다.

 

수행시간)

모든 원소를 다 돌아다니므로, 1+2+3+4+5+6+...+n 이 된다. (n=높이)

이것은 h*(h+1)/2 가 되므로, 수행시간은 O(n*n) 이 된다.

 

코드)

 

#include <string>
#include <vector>
#include<algorithm>
using namespace std;

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

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    //맨 꼭대기 dp초기화
    dp[0][0]=triangle[0][0];
    
    for(int i=1;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++){
            //각 줄의 처음 원소
            if(j==0){
                dp[i][j]=triangle[i][j]+dp[i-1][j];
            }
            //각 줄의 마지막 원소
            else if(j==triangle[i].size()-1){
                dp[i][j]=triangle[i][j]+dp[i-1][j-1];
            }
            else{
                dp[i][j]=triangle[i][j]+max(dp[i-1][j],dp[i-1][j-1]);
            }
        }
    }
    
    //마지막 줄을 돌아다니며 최대값 찾음
    int ind=triangle.size()-1;
    answer=*max_element(dp[ind],dp[ind]+ind+1);
    return answer;
}

 

실행결과)