[Inflearn] 알리바바와 40인의 도둑(DP : Bottom-Up)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 해당 돌다리를 건널 때 돌의 높이 만큼 에너지가 소비

- 이동은 최단 거리 이동

- 현재 지점에서 오른쪽 도는 아래쪽으로만 이동

- 출발점에서 도착점까지 가는데 드는 에너지의 최소량

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

DP Bottom-Up 방식으로 풀어보자.

작은 문제부터 차근차근 해결하여 큰 문제를 해결해야 한다.

여기서는 가까운 지점까지의 최소 에너지를 구하면서 

차근차근 최종 도착점까지의 최소 에너지를 구해내는 방식으로 접근하면 된다.

입력이 아래 그림과 같을 때,

먼저 map(0,0)은 출발 지점이므로 dp(0,0)에 저장해준다.

여기서 다음 map(0,1) 지점은 위에서 오거나 왼쪽에서 오는 경우이다.

그런데 위 지점은 영역 밖이므로 왼쪽에서 오는 경우 뿐이다.

왼쪽에서의 최소 에너지는 3이므로 3 + 현재 돌 높이를 해주면 된다.

다음도 마찬가지로 왼쪽에서 오는 경우 뿐이다.

사실 0행과 0열은 한쪽 방향으로만 올 수 있으므로 계속 누적해주면 된다.

이제 위, 왼쪽 방향에서 모두 올 수 있는 map(1,1)부터가 중요하다.

위에서 오는 경우는 즉, (0,0) (0,1)을 거쳐서 온 경우는 에너지가 6 소모되고

왼쪽에서 오는 경우는 즉 (0,0) (1,0)을 거쳐 온 경우 에너지가 5 소모되었다.

(0,0) (1,0)을 거쳐 온 경로가 더 적은 에너지(5)가 소모되었다.

그럼 해당 값에 현재 돌 높이를 더해주면 된다.

(1, 2)의 경우도 마찬가지이다.

위에서 오는 경우는 즉, (0,0) (0,1) (0,2)를 거쳐서 온 경우는 에너지가 11 소모되고

왼쪽에서 오는 경우는 즉 (0,0) (1,0) (1,1) 을 거쳐 온 경우 에너지가 8 소모되었다.

(0,0) (1,0) (1,1) 을 거쳐 온 경로가 더 적은 에너지(8)가 소모되었다.

그럼 해당 값에 현재 돌 높이를 더해주면 된다.

이렇게 진행하다보면 아래와 같은 결과가 나오게 될 것이다.

#. Code

ㅇ 초기 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define f first
#define s second
#define MAX 2147000000
#define MIN -2147000000
 
int dx[] = { -1, 0 }, dy[] = { 0, -1 };
 
int main(void)
{
    int n, i, j, x, y, mn;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    vector<vector<int> > map(n, vector<int>(n));
    vector<vector<int> > dp(n, vector<int>(n));
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            scanf("%d", &map[i][j]);
    
    dp[0][0] = map[0][0];
    for (i = 1; i < n * n; i++) {
        x = i / n;
        y = i % n;
        mn = MAX;
 
        for (j = 0; j < 2; j++) {
            int xx = x + dx[j];
            int yy = y + dy[j];
 
            if (xx < 0 || yy < 0) continue;
 
            mn = min(mn, dp[xx][yy]);
        }
 
        dp[x][y] = mn + map[x][y];
    }
 
    printf("%d\n", dp[n-1][n-1]);
 
    return 0;
}

ㅇ최적화 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    int n, i, j;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    vector<vector<int> > map(n, vector<int>(n));
    vector<vector<int> > dp(n, vector<int>(n));
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            scanf("%d", &map[i][j]);
    
    dp[0][0] = map[0][0];
    // 가장자리인 0행, 0열 선 처리
    for (i = 1; i < n; i++) {
        dp[0][i] = dp[0][i - 1] + map[0][i];
        dp[i][0] = dp[i - 1][0] + map[i][0];
    }
 
    for(i = 1; i < n; i++) {
        for (j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + map[i][j];
        }
    }
 
    printf("%d\n", dp[n-1][n-1]);
 
    return 0;
}

line 17) 직관적으로 풀 수 있는 가장 작은 문제의 해를 구해놓는다.

line 19~22) 가장자리는 한 방향으로만 이동할 수 있기 때문에 선처리를 할 수 있다.

    선처리를 하게되면 입력이 커질 시 시간복잡도를 줄일 수 있으므로 해주는게 좋다.

    * 초기 코드에서는 그냥 하긴 했는데.. 사실 생각도 못 했었다ㅋㅋ..

line 24~28) 가장자리는 선처리가 되어있기 때문에 (1, 1)부터 문제를 해결하면 된다.

위쪽 or 왼쪽 좌표까지 도달하는데 소모된 최소 에너지에 현재 돌 높이를 더해준 값을 기록해준다.

#. Teach code

#include<bits/stdc++.h>
using namespace std;
 
int arr[21][21], dy[21][21];
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>arr[i][j];
        }
    }
    dy[0][0]=arr[0][0];
    for(int i=1; i<n; i++){
        dy[0][i]=dy[0][i-1]+arr[0][i];
        dy[i][0]=dy[i-1][0]+arr[i][0];
    }
    for(int i=1; i<n; i++){
        for(int j=1; j<n; j++){
            dy[i][j]=min(dy[i-1][j], dy[i][j-1])+arr[i][j];
        }
    }
    cout<<dy[n-1][n-1];
    return 0;
}

#. Result

  - Input --------------------------------------------------------

5

3 7 2 1 9

5 8 3 9 2

5 3 1 2 3

5 4 3 2 1

1 7 5 2 4

------------------------------------------------------------------

  - Output --------------------------------------------------------

25

------------------------------------------------------------------