[백준 11048] 이동하기

www.acmicpc.net/problem/11048

11048번: 이동하기

 

이문제는 모든 경우의 수를 다루는 DP(Dynamic Programming) 알고리즘을 사용하여 풀 수 있다.

처음에 나의 접근 방법은 데이터를 다 받은 뒤에,

시작에서 끝으로 퍼져나가는 방식을 고려하여 풀려고 했다.

 

처음 코드

---

#include <iostream>

using namespace std;

#define MAX_SIZE  1000

int g_nMap[MAX_SIZE][MAX_SIZE];

int MaximumPath(int r, int c, int n, int m, int val)
{
    if(r == n-1 && c == m-1)
    {
        return val;
    }
    else
    {
        int x = 0, y = 0, z = 0;
        int max  = 0;

        if(r < n-1)
            x = MaximumPath(r+1, c, n, m, val + g_nMap[r+1][c]);       
        if(c < m-1)
            y = MaximumPath(r, c+1, n, m, val + g_nMap[r][c+1]);     
        if(r < n-1 && c < m-1)
            z = MaximumPath(r+1, c+1, n, m, val + g_nMap[r][c+1]);      

        if(max < x)
            max = x;
        if(max < y)
            max = y;
        if(max < z)
            max = z;

        return max;
    }  
}

int main(void)
{
    int n = 0;
    int m = 0;
    
    cin >> n >> m;

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

    cout << MaximumPath(0, 0, n, m, g_nMap[0][0]) << endl;
    
    return 0;
}

---

 

이렇게 풀어보니 "시간 초과" 에러가 나는 것이다.

그래서 아 모든 경우를 고려하는게 아닌 Greedy 방법인가 했지만 경우의 수를 따져보았을때 

아닌거 같아 다른 블로그를 찾아봤다.

 

여기서는 데이터를 받으면서 동시에 맵을 업데이트를 하는 방법으로 각셀의 값이아닌

비교한 뒤 바로 최대값을 입력하는 방식이였다.

 

 

 

수정한 코드

---

#include <iostream>

using namespace std;

#define MAX_SIZE  1001

int g_nMap[MAX_SIZE][MAX_SIZE];

int Get_MaxNum(int x, int y, int z)
{
    int max = 0;

    if(max < x)
        max = x;
    if(max < y)
        max = y;
    if(max < z)
        max = z;
    
    return  max;
}

int main(void)
{
    int n = 0;
    int m = 0;

    cin >> n >> m;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
        
            int tmp = 0;
            int max = 0;
            cin >> tmp;
            max = Get_MaxNum(g_nMap[i-1][j], g_nMap[i-1][j-1], g_nMap[i][j-1]);

            g_nMap[i][j] = max + tmp;
        }
    }

    cout << g_nMap[n][m] << endl;

    return 0;
}

---

 

역시 세상엔 똑똑한 사람들이 많다.. 많이 보고 배워야지 ..ㅎㅎ