백준 11048 이동하기 c++

 

 

 

처음 작성한 코드는 다음과 같다.

#include <iostream>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    
    int arr[n+1][m+1];
    int dp[n+1][m+1];
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
            dp[i][j] = arr[i][j];
        }
    }
    
    int max = dp[n][m];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(i+1 <= n)
                dp[i+1][j] += dp[i][j];
            if(j+1 <= m)
                dp[i][j+1] += dp[i][j];
            if( (i+1<=n) && (j+1<=m) )
                dp[i+1][j+1] += dp[i][j];           
            
            if(i==n && j==m){
                if(max < dp[n][m])
                    max = dp[n][m];
            }
        }
    }
    
    cout << dp[n][m];
    return 0;
}

 

 

 

하지만 틀렸다는 결과가 나왔다.

다시 작성한 코드는 다음과 같다.

현재에서 다음 배열을 계산하는게 아니라, 다음 배열로 와서 전의 값들을 고려해주는 방식으로 구현하면 

더 간단하게 할 수 있었다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;
    
    int arr[1001][1001];
    int dp[1001][1001];
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    
    int temp;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            temp = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
            dp[i][j] = temp + arr[i][j];
        }
    }
    
    cout << dp[n][m];
    return 0;
}