문제

동적 계획법(DP)을 사용하는 문제

1. 최대 높이가 500인 삼각형이 주어집니다. (1 <= n <= 500)

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

3. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.

4. 제일 아래까지 이동했을때 거쳐간 수들의 합중 최대값을 구하시오.

• 문제링크

---

풀이 과정

1. 알고리즘

최대값, 최소값 이런거 구하라고 나오면 왠만해서는 DP
그리고, 이런 문제일 경우 문제에서 점화식을 알려줍니다.

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.

그럼 동적 계획법을 사용해봅시다.

2. 자료구조

이차원 배열에 삼각형을 저장해줍니다.

3. 점화식

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.

문제에 따라 점화식을 만들면 다음과 같습니다.

단, 왼쪽 제일끝, 오른쪽 제일끝은 하나만 받을 수 있도록 예외처리 해주었습니다.

// d[i][j]에는 i, j에서의 합중 최대값을 저장합니다.
// 1) 삼각형 제일 왼쪽 끝인 경우
if(j == 0){
	d[i][j] = d[i-1][j] + triangle[i][j];
// 2) 삼각형 제일 오른쪽 끝인 경우
}else if(j == i){
	d[i][j] = d[i-1][j-1] + triangle[i][j];
}
// 3) 삼각형 왼쪽, 오른쪽 끝인 아닌 내부인 경우
else{
	d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j];
}

점화식 설계했으니까 2중 for문으로 삼각형을 순회하면서 점화식을 수행해줍니다.

4. 시간 복잡도

삼각형의 높이 최대값은 500
2차원 배열에 저장해놓고 500*500 을 이중 for문으로 순회한다면 O(n^2) = O(250000)

1억에 1초니까 25만이면 시간안에 충분히 풀 수 있습니다.

5. C++

1) Bottom up - 반복문

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

using namespace std;
/*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n^2)
    사용한 알고리즘: DP(bottom-up)
    사용한 자료구조: 2차원 배열
*/

int answer, height, d[max_int][max_int];

int max(int a, int b){
    return a > b ? a : b;
}

int solution(vector<vector<int>> triangle) {
    // 예외 사례, 초기값을 설정해준다.
    answer = d[0][0] = triangle[0][0];
    // 삼각형의 높이를 계산한다.
    height = (int)triangle.size();
    
    for(int i=1; i<height; i++){
        for(int j=0; j<=i; j++){
            // 1) 삼각형 제일 왼쪽 끝인 경우
            if(j == 0){
                d[i][j] = d[i-1][j] + triangle[i][j];
            // 2) 삼각형 제일 오른쪽 끝인 경우
            }else if(j == i){
                d[i][j] = d[i-1][j-1] + triangle[i][j];
            }
            // 3) 삼각형 왼쪽, 오른쪽 끝인 아닌 내부인 경우
            else{
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j];
            }
            
            // 최대값 갱신
            answer = max(answer, d[i][j]);
        }
    }
        
    return answer;
}

2) Top-down - 재귀

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

using namespace std;
/*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n^2)
    사용한 알고리즘: DP(top-down)
    사용한 자료구조: 2차원 배열
*/


int answer, height, a[max_int][max_int], d[max_int][max_int];

int max(int a, int b){
    return a > b ? a : b;
}

int go(int i, int j){
    
    // 예외 사례 (0, 0)일 경우 현재의 값을 반환한다.
    if(i == 0 && j == 0) return d[i][j];
    
    // 메모이제이션, 이미 계산한 결과일 경우, 저장된 값을 반환한다.
    if(d[i][j] > 0) return d[i][j];
    
    for(int j=0; j<=i; j++){
        // 1) 삼각형 제일 왼쪽 끝인 경우
        if(j == 0){
            d[i][j] = go(i-1, j) + a[i][j];
        // 2) 삼각형 제일 오른쪽 끝인 경우
        }else if(j == i){
            d[i][j] = go(i-1, j-1) + a[i][j];
        }
        // 3) 삼각형 왼쪽, 오른쪽 끝인 아닌 내부인 경우
        else{
            d[i][j] = max(go(i-1, j-1), go(i-1, j)) + a[i][j];
        }
    }
    return d[i][j];
}

int solution(vector<vector<int>> triangle) {
    // 예외 사례, 초기값을 설정해준다.
    d[0][0] = triangle[0][0];
    // 삼각형의 높이를 계산한다.
    height = (int)triangle.size();
    
    /*
     최대 500 * 500인 벡터를 재귀호출때 마다 인자값으로 넣어주면 시간초과 걸린다.
     전역변수에 넣어주었다.
     */
    for(int i=0; i<height; i++){
        for(int j=0; j<=i; j++){
            a[i][j] = triangle[i][j];
        }
    }
    
    // 제일 아래층에 대해서 재귀호출을 수행한다.
    for(int j=0; j<height; j++){
        answer=max(answer, go(height - 1, j));
    }
        
    return answer;
}