[ 백준 ] 10164 / 격자상의 경로

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
135/228
post-thumbnail

# Appreciation

/*
 * Problem :: 10164 / 격자상의 경로
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 전형적인 DP 문제이다
 *   + dp[i][j] = (i, j) 좌표까지 이동할 수 있는 서로 다른 경로의 개수
 *     # dp[i][j] = dp[i-1][j] + dp[i][j-1]
 *
 * - 입력이 3 5 8 인 경우
 *   + 1 1 1 0 0
 *     1 2 3 3 3
 *     0 0 3 6 9
 *   입력이 3 5 9 인 경우
 *   + 1 1 1 1 0
 *     1 2 3 4 4
 *     0 0 0 4 8
 *     # (첫 칸) -> (반드시 지나가야 하는 칸)
 *       으로 DP 를 돌린 후,
 *       (반드시 지나가야 하는 칸) -> (마지막 칸)
 *       으로 한번 더 DP 를 돌려준다
 *
 * Point
 * - 문제를 기준으로 첫 칸은 (1,1) 이지만
 *   편의상 코드에서는 (0,0) 으로 간주하고 풀었다
 *
 * - 입력이 15 15 1 인 경우 40116600 이고
 *   입력이 15 15 2 인 경우 20058300 이니
 *   Overflow 걱정없이 int 를 쓰자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M, K;
    cin >> N >> M >> K;

    // Process
    /* 첫 칸을 (0,0) 으로 하였을 때 기준 */
    int ky = (K == 0) ? 0 : (K-1) / M;
    /* K 가 0 이면 그냥 첫 칸을 반드시 지나가야 하는 칸으로 설정 */
    int kx = (K == 0) ? 0 : (K-1) % M;

    int dp[N][M];
    memset(dp, 0, sizeof(dp));

    /* (첫 칸) -> (반뜨시 지나가야 하는 칸) DP 초기화 */
    for (int i=0; i<=ky; i++) {
        dp[i][0] = 1;
    }
    for (int j=0; j<=kx; j++) {
        dp[0][j] = 1;
    }
    /* 현재 상태 (입력 3 5 8 기준) - 반드시 지나가야하는 칸은 [] 표시
     * 1  1  1  0  0
     * 1  0 [0] 0  0
     * 0  0  0  0  0 */

    /* (첫 칸) -> (반드시 지나가야 하는 칸) DP 실행 */
    for (int i=1; i<=ky; i++) {
        for (int j=1; j<=kx; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    /* 현재 상태 (입력 3 5 8 기준) - 반드시 지나가야하는 칸은 [] 표시
     * 1  1  1  0  0
     * 1  2 [3] 0  0
     * 0  0  0  0  0 */

    /* (반드시 지나가야 하는 칸) -> (마지막 칸) DP 초기화 */
    for (int i=ky+1; i<N; i++) {
        dp[i][kx] = dp[ky][kx];
    }
    for (int j=kx+1; j<M; j++) {
        dp[ky][j] = dp[ky][kx];
    }
    /* 현재 상태 (입력 3 5 8 기준) - 반드시 지나가야하는 칸은 [] 표시
     * 1  1  1  0  0
     * 1  2 [3] 3  3
     * 0  0  3  0  0 */

    /* (반드시 지나가야 하는 칸) -> (마지막 칸) DP 실행 */
    for (int i=ky+1; i<N; i++) {
        for (int j=kx+1; j<M; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    /* 현재 상태 (입력 3 5 8 기준) - 반드시 지나가야하는 칸은 [] 표시
     * 1  1  1  0  0
     * 1  2 [3] 3  3
     * 0  0  3  6  9 */

    // Control : Output
    cout << dp[N-1][M-1] << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글