(C++) - 백준(BOJ) 14494번 : 다이나믹이 뭐에요?

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

14494번: 다이나믹이 뭐예요?

기본 dp문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. i행, j열에 도달할 경우의 수를 저장하기 위한 이차원 배열 d와 n, m을 선언합니다.

 2. d의 모든 원소들을 -1로 초기화해줍니다.

 3. n, m을 입력해줍니다.

 

📔 풀이과정

 1. dp함수를 수행합니다.

 

 2. n행 m열에서 출발해 역(1행 1열)로 거슬러 올라가며 dp함수를 호출합니다.

 

 3. 1행 1열에 알맞게 도착했다면 1을, 열,행 둥 중 하나라도 음수라면 0을 반환해줍니다.

d는 1, 1에서 i, j에 도착하는 경우의 수입니다. i,j로 오려면 직전에는 →, ↓, ↘ 이 세 방향으로 이동해야합니다. 점화식을 세워본다면 이렇습니다. 

d[i][j] = d[i-1][j] (i-1,j에서 →방향으로 옴) + d[i-1][j] (i-1, j에서 ↓로옴) + d[i-1][j-1] (i-1, j-1에서 ↘로옴)

* (d[i-1][j] + d[i-1][j] % MOD) + d[i-1][j-1]) % MOD 가 답입니다. 세 항을 모두 더했을 때 int범위를 초과할 수 있기 때문입니다.

 

 4. 이를 수행한 결과를 반환합니다.

 

📔 정답출력

 dp함수의 결과값을 출력합니다.

---

📕 Code

Top Down

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int d[1001][1001], n, m;

int dp(int i, int j){
    if(i < 1 || j < 1) return 0;
    if(i == 1 && j == 1) return 1;
    int &ret = d[i][j];
    if(ret != -1) return ret;
    ret = 0;
    ret = ((dp(i,j-1) + dp(i-1,j)) % MOD + dp(i-1,j-1)) % MOD;
    return ret;
}

int main(){
    memset(d,-1,sizeof(d));
    cin >> n >> m;
    cout << dp(n,m);
}