BOJ : 11048 이동하기

 

---

[BOJ 11048(S1) 리뷰]

이번 DP문제는 Top-down 방식과 Bottom-up 방식 두가지로 풀어보려고 한다.

문제는 N*M 행렬이 주어지고 각각의 좌표마다 value가 존재할때 (1,1)부터 (N,M)까지 갈때의 최대값을 구해야 한다.

다음 좌표로 이동할땐 (R+1,C) , (R,C+1) , (R+1,C+1)로 이동이 가능하다. 즉 아래,오른쪽,오른쪽 대각선 아래로만 이동을 해야 한다.

 

먼저 Top-down의 코드이다.

#include <bits/stdc++.h>
using namespace std;
int arr[1001][1001];
int dp[1001][1001];
int N, M;

int solve(int r, int c)
{
    if (r + 1 > N && c + 1 > M) return arr[r][c];
    if (r > N+1  || c > M+1) return 0;
    if (dp[r][c]!= -1) return dp[r][c];
   
    return dp[r][c]=max({ solve(r + 1,c),solve(r,c + 1),solve(r + 1,c + 1) }) + arr[r][c];
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
            cin >> arr[i][j];
    }

    for (int i =1; i <= N; i++)
        fill(dp[i], dp[i] + M+1, -1);


    cout << solve(1, 1);
} 

먼저 메모이제이션을 이용하기 위해 main함수 내에서 fill을 통해 -1로 초기화 한다음 solve를 호출한다.

solve는 좌표밖으로 나가면 0을 리턴하며 현재 자신의 위치를 더하며 세가지 방향에 대해 재귀호출을 한다.

이러면 solve함수가 종료되었을때 우리는 최대값을 return받을 수 있다.

 

다음은 Bottom-up 방식이다.

#include <bits/stdc++.h>
using namespace std;
int arr[1001][1001];
int dp[1001][1001];
int N, M;


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
            cin >> arr[i][j];
    }

    
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            dp[i][j] = max({ dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1] }) + arr[i][j];
        }
    }

    cout << dp[N][M];

   
} 

Top-down방식이 도착점까지 간 후에 최대값을 더하며 시작점으로 돌아왔다면

Bottom-up방식은 시작점부터 목적지까지 가며 자신이 전에 있었던 위치 중 최대값을 더하며 내려 간다.

목적지인 dp[N][M]에 담긴 값이 최대값이 된다.

 

---