DP 경로구하기

https://www.youtube.com/watch?v=j_sdjivoPs8 

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

int arr[5][5];
int dp[5][5];
char P[5][5];


void path(int x, int y){
    if(x==1 && y==1){
        cout << x << ' ' << y << '\n';
        return;
    }
    else if(P[x][y]=='^'){
        path(x-1,y);
    }
    else if(P[x][y]=='<'){
        path(x,y-1);
    }

    cout << x << ' ' << y << '\n';
    return;
}


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

    arr[1][1] = 6;
    arr[1][2] = 7;
    arr[1][3] = 12;
    arr[1][4] = 5;
    arr[2][1] = 5;
    arr[2][2] = 3;
    arr[2][3] = 11;
    arr[2][4] = 18;
    arr[3][1] = 7;
    arr[3][2] = 17;
    arr[3][3] = 3;
    arr[3][4] = 3;
    arr[4][1] = 8;
    arr[4][2] = 10;
    arr[4][3] = 14;
    arr[4][4] = 9;



    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            if(i==1 && j==1) dp[i][j] = arr[i][j];
            else if(i==1) dp[i][j] = arr[i][j] + dp[i][j-1];
            else if(j==1) dp[i][j] = arr[i][j] + dp[i-1][j];
            else dp[i][j] = arr[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << '\n';

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }


    int x=4, y=4;



    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            if(i==1 && j==1) P[i][j] = '-';
            else if(dp[i-1][j] < dp[i][j-1] || j==1){
                P[i][j] = '^';
            }
            else{
                P[i][j] = '<';
            }
        }
    }

    cout << '\n';

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << P[i][j] << ' ';
        }
        cout << '\n';
    }


    path(4, 4);

    return 0;
}