[코드트리 챌린지] 정수 사각형 최소 합

[실력진단 테스트]

[문제]

https://www.codetree.ai/missions/2/problems/minimum-sum-path-in-square?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

(1,N) 에서 (N,1) 로 이동을 할 때 거쳐간 숫자의 최소합을 구하는 문제이다.

이동은 왼쪽 혹은 밑으로만 가능하다.

범위가 100 * 100이기 때문에 이를 모두 완전탐색으로 구하게 되면 2 ^ 100승이 넘어가는 숫자가 나오게 되므로 시간초과에 걸리게 된다.

그러니 DP 테이블을 이용해서 해당 문제를 풀도록 하자.

 

 

그렇게 우선 DP 테이블의 가장 위와 가장 우측을 boards를 이용해서 이전 숫자를 더해준 DP 테이블로 만들어주자.

 

우리가 마지막에 만들 DP 테이블은 아래와 같다.

 

 

이를 이용해 DP[i][j] = max(DP[i - 1][j] , DP[i][j+1]) + boards[i][j] 라는 점화식을 만들 수 있다.

이제 이를 코드에 적용을 해주자.

[회고]

.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int boards[105][105];
int dp[105][105];

int main() {
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>boards[i][j];
        }
    }

    dp[0][n - 1] = boards[0][n-1];

    for(int i = n - 2;i>=0;i--){
        dp[0][i] = boards[0][i] + dp[0][i + 1];
    }
    
    for(int i = 1;i<n;i++){
        dp[i][n -1] = boards[i][n-1] + dp[i - 1][n - 1];
    }

    for(int i = 1;i<n;i++){
        for(int j = n - 2;j>=0;j--){
            dp[i][j] = min(dp[i - 1][j], dp[i][j + 1]) + boards[i][j];
        }
    }

    cout<<dp[n - 1][0]<<endl;

    return 0;
}