[코드트리 챌린지] 3주차 DP l - 격자 안에서 한 칸씩 전진하는 DP / 정수 사각형 최소 합

 

https://www.codetree.ai/missions/2/problems/minimum-sum-path-in-square/description

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

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[105][105]; // 행렬 저장용
int dp[105][105]; // 숫자 합 dp

void Initialize() {
    // dp 초기값 설정
    dp[0][n-1] = arr[0][n-1];

    // 첫 번째 줄 가로, 세로를 채우는 방법은 하나밖에 없으므로
    // 모두 채움
    for (int i = 1; i < n; i++) {
        dp[i][n - 1] = dp[i - 1][n - 1] + arr[i][n - 1];
    }
    for (int i = n-2; i >= 0; i--) {
        dp[0][i] = dp[0][i + 1] + arr[0][i];
    } 
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    Initialize();

    /*
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    */
    
    
    
    // 위, 우측중 어느 부분에서 내려와야 값이 작아지는지 판단하여 저장
    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]) + arr[i][j];
        }
    }

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

}

n을 입력받아 n x n 행렬을 채우도록 합니다.

Initialize() 함수를 통해 초기값을 설정합니다.

dp[0][n-1]이나 dp[0][i] , dp[i][n-1] 같은 경우 쭉 왼쪽으로 진행하거나 아래로 진행하는 방법 밖에
존재하지 않으므로 for문을 통해 dp 배열을 채우도록 합니다.

그 후 이중 for문을 통해 왼쪽에서 와야 작은지 위쪽에서 와야 값이 작아지는지 비교하여 dp 배열을 채우도록 합니다.

dp[n-1][0]을 출력합니다.