백준 11048 이동하기(dynamic programming)

 

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

11048번: 이동하기

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX = 1000 + 1;
int N, M;
int arr[MAX][MAX];
int cache[MAX][MAX];

void sumofCandy()
{

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (i == 1 && j == 1)
                cache[i][j] = arr[1][1];
            else
                cache[i][j] = max(max(cache[i - 1][j], cache[i][j - 1]), cache[i - 1][j - 1]) + arr[i][j];
        }
    }
    cout << cache[N][M];
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> arr[i][j];
    memset(cache, -1, sizeof(cache));
    sumofCandy();
}

 

자꾸 오류가 나던 colorscripter를 버리고 코드를 예쁘게 올리는 다른 방법을 찾아냈다. 진작에 했어야 했는데 게을러서 이제야 했다.

 

이 문제는 정말 오로지 혼자 힘으로 금방 풀었다... 뭔가 계속 dp문제만 푸니까 익숙해져서 그런가 쉽게 쉽게 풀려서 기분이 좋았다.

 

굉장히 쉬운 개념이었다. 가장 먼저 두 개의 테이블을 그리고 본래 입력의 배열과 각각의 자리에서 가질 수 있는 최대 사탕의 개수를 적어봤다.

 

1	2	3	4
0	0	0	5
9	8	7	6

 

1	3	6	10
1	3	6	15
10	18	25	31

 

이 테이블 2개만 보고도 각 자리에서 최대로 가질 수 있는 사탕의 개수는 max(윗칸, 왼쪽칸, 왼쪽위칸) + 원래 그 자리의 사탕개수임을 알 수 있었다.

 

즉 cache[i][j] = max(cache[i-1][j], cache[i][j-1], cache[i-1][j-1]) + arr[i][j] 라는 점화식을 도출할 수 있다.

 

  cache[1][1] = arr[1][1];
    for (int i = 2; i <= M; i++)
        cache[1][i] = cache[1][i - 1] + arr[1][i];
    for (int j = 2; j <= N; j++)
        cache[j][1] = cache[j - 1][1] + arr[j][1];

 

처음에는 이런 식으로 첫 가로줄과 첫 세로줄을 초기화했다. 다 해놓고보니 코드가 너무 더러워보이기도 했고 arr 배열의 0번째 행과 열이 비어있는 것이 보였다. 때문에 이 빈 칸들을 모두 -1로 초기화하여 조금 더 깔끔하게(?) 코드를 짯다.

 

이차원 배열을 쓸 때 항상 동적인 vector를 사용해야 할지 정적이게 미리 int형으로 선언해야 할지 고민된다. 아직 지식이 부족해서 그런것 같은데 조금 더 고민하는 과정이 필요하겠다.