[백준 12181번] [동적 계획법] Googlander (Large)

Approach

한 점을 기준으로 가능한 경우는 2가지 밖에 없다.

• 현재 방향으로 이동
• 현재 방향에서 오른쪽으로 이동

잘 생각해보면, 전자의 경우는 행이 주는 경우이고 후자의 경우는 열이 주는 경우이다.

그리고 바라보는 방향은 크게 중요하지는 않은데 왜냐하면 대칭이기 때문이다.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (if i or j == 1, dp[i][j] = 1)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    int t;
    cin >> t;
    long long dp[26][26];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i <= 25; i++)
    {
        dp[1][i] = 1;
        dp[i][1] = 1;
    }

    for (int r = 2; r <= 25; r++)
    {
        for (int c = 2; c <= 25; c++)
        {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }

    for(int i = 1; i <= t; i++){
        int r, c;
        cin >> r >> c;
        cout << "Case #" << i << ": " << dp[r][c] << "\n";
    }

    return 0;
}