c++ 백준 11048 이동하기 | DP

문제

www.acmicpc.net/problem/11048

11048번: 이동하기

 

풀이 방법

 

DP 라는 이름의 테이블을 하나 만든다. DP[N][M]

DP[i][j]는 (i,j)까지 이동할 때, 가져 올 수 있는 사탕 개수의 최댓값을 저장한다.

 

(0,0) -> (1, 0) 로 이동할 때 사탕 값 업데이트,

(0,0) -> (0, 1) 로 이동할 때 사탕 값 업데이트,

(0,0) -> (1, 1) 로 이동할 때 사탕 값 업데이트,

 

(1,0) -> (2, 0) 로 이동할 때 사탕 값 업데이트,

(1,0) -> (1, 1) 로 이동할 때 사탕 값 업데이트,

(1,0) -> (2, 1) 로 이동할 때 사탕 값 업데이트,

 

...

 

구현 코드

#include <iostream>

using namespace std;

int main()
{
    // init
    int array[1000][1000] = { 0, };
    int table[1000][1000] = { 0, };
    
    int N = 0;
    int M = 0;
    
    // get input
    cin >> N >> M;
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> array[i][j];
        }
    }
    
    //calculate table
    table[0][0] = array[0][0];
    
    int xPosition[3] = {0, 1, 1};
    int yPosition[3] = {1, 0, 1};
            
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            // right, bottom, right bottom
            for(int a=0; a<3; a++)
            {
                int x = i + xPosition[a];
                int y = j + yPosition[a];
                
                // exception
                if( x<0 || y<0 || x>=N || y>=M )
                {
                    continue;
                }
                
                if( table[i][j]+array[x][y] > table[x][y] )
                {
                    table[x][y] = table[i][j]+array[x][y];
                }
            }
        }
    }
    
    cout << table[N-1][M-1] <<endl;
    
    return 0;
}