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

#. 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

Bottom-up으로 풀었던 문제를 Top-Down방식으로 풀어보자.

입력이 아래와 같을 때,

DFS()의 동작을 트리로 그려보면 아래 그림과 같다.

자식 트리의 두 결과에서

작은 값에 현재 돌다리 높이를 더해주면 지금까지의 최소 에너지가 된다.

여기서 메모이제이션을 이용하면 이미 연산했던 결과를 또 연산하지 않아도 되므로

시간복잡도를 줄일 수 있다.

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
int n;
vector<vector<int> > map, dp;
 
int DFS(int idx)
{
    int x = idx / n;
    int y = idx % n;
 
    if (x == 0 && y == 0) return dp[0][0];
    if (x < 0 || x >= n || y < 0 || y >= n) return MAX;
    if (dp[x][y]) return dp[x][y];
 
    return dp[x][y] = min(DFS(idx - 1), DFS(idx - n)) + map[x][y];
}
 
int main(void)
{
    int i, j;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    map.resize(n, vector<int>(n));
    dp.resize(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];
    DFS(n*n-1);
 
    printf("%d\n", dp[n-1][n-1]);
 
    return 0;
}
 

ㅇ코드 최적화

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
int n;
vector<vector<int> > map, dp;
 
int DFS(int idx)
{
    int x = idx / n;
    int y = idx % n;
 
    if (x == 0 && y == 0) return map[0][0];
    if (dp[x][y]) return dp[x][y];
 
    if (!y) return dp[x][y] = DFS(idx - n) + map[x][y];
    else if (!x)  return dp[x][y] = DFS(idx - 1) + map[x][y];
    else return dp[x][y] = min(DFS(idx - 1), DFS(idx - n)) + map[x][y];
}
 
int main(void)
{
    int i, j;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    map.resize(n, vector<int>(n));
    dp.resize(n, vector<int>(n));
 
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            scanf("%d", &map[i][j]);    
 
    printf("%d\n", DFS(n * n - 1));
 
    return 0;
}
 

line 16) x, y가 0일 경우, map[0][0]값을 return

line 17) 메모이제이션에 저장된 값이 있다면 재사용

line 19~21) x가 0일 경우, y가 0일 경우, x,y가 0이 아닐 경우 나누어서 진행

    (재귀함수의 깊이를 줄이기 위함)

line 19) y가 0일 경우, 위쪽만 탐색

line 20) x가 0일 경우, 왼쪽만 탐색

line 21) 그 외의 경우 왼쪽, 위쪽을 탐색

#. Teach code

#include<bits/stdc++.h>
using namespace std;
int arr[21][21], dy[21][21];
 
int DFS(int x, int y){
    if(dy[x][y]>0) return dy[x][y];
    if(x==0 && y==0){
        return arr[0][0];
    }
    else{
        if(y==0) return dy[x][y]=DFS(x-1, y)+arr[x][y];
        else if(x==0) return dy[x][y]=DFS(x, y-1)+arr[x][y];
        else return dy[x][y]=min(DFS(x-1, y), DFS(x, y-1))+arr[x][y];
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    int n, cnt=0;
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>arr[i][j];
        }
    }
    cnt=DFS(n-1, n-1);
    cout<<cnt;
    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

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