[11048] 이동하기

https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

---

 

🔎 해결 방법

(1, 1)에서부터 (n, m)까지 가면서 오른쪽, 대각선, 아래쪽 중 가장 큰 값을 더해나가면 되지 않을까? 그럼 dp가 필요없는데? 라고 생각했지만

이 문제를 dp로 풀어야 하는 이유가 있다.

만약의 미로가 위와 같이 주어졌다면,

 

현재 내 위치에서 갈 수 있는 칸 중 가장 최댓값만 취해서 이동한다면 위와 같이 되고,

이것은 dp가 아니라 그리디 알고리즘이라고 할 수 있을 것이다.

하지만 당연하게도 이것은 정답이 아니고ㅋㅋ

 

위와 같은 경우가 최댓값을 얻을 수 있는 경우이다. 

(1, 1)에서 다음 칸으로 이동할 때 현재 위치에서 가장 최댓값을 얻으려면 (1, 2)로 이동해야 하지만,

장기적으로 봤을 때는 (2, 1)로 이동하는 것이 더욱 효율적인 것이다.

즉, 모든 경우를 다 고려해야 하는 dp를 사용해야 한다!

 

점화식은 매우 간단하다.

dp[i][j] = max(dp[i - 1][j], dp[i - 1], dp[j - 1], dp[i][j - 1]) + candy[i][j]

 

현재 위치까지의 최댓값을 구하기 위해서는

dp[i - 1][j], dp[i - 1], dp[j - 1], dp[i][j - 1] 중 최댓값을 찾고

여기에 현재 칸에 놓여있는 사탕의 개수를 더해주면 끝!

 

<algorithm> 헤더에 내장되어 있는 max 함수는 인자가 두 개일때만 사용할 수 있기 때문에 

여기서는 max 함수를 따로 구현해줘야 한다. (아래 코드 참고)

 

---

 

💡 내 코드(C++)

// [11048] 이동하기
// https://www.acmicpc.net/problem/11048

#include <iostream>
using namespace std;
int max(int a, int b, int c);

int main(void)
{
    int n, m, tmp;
    int candy[1002][1002], dp[1002][1002];
    cin >> n >> m;
    
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= m ; j++) {
            cin >> tmp;
            candy[i][j] = tmp;
        }
    }
    
    dp[0][0] = 0, dp[0][1] = 0, dp[1][0] = 0;
    
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= m ; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + candy[i][j];
        }
    }

    cout << dp[n][m];
}

int max(int a, int b, int c)
{
    int maxValue = a;
    
    if(b > maxValue)
        maxValue = b;
    if(c > maxValue)
        maxValue = c;

    return maxValue;
}