백준 10164 격자상의 경로

문제 링크입니다: https://www.acmicpc.net/problem/10164

이산수학에서 배운 조합을 쓴다면 훨씬 간단하게 풀 수 있는 문제입니다.

하지만 동적계획법을 연습하고 싶은 관계로 다음과 같이 풀었습니다.

*(x+1)+y*M이 격자 안에 있는 숫자입니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 15;

 

int N, M, K; //두 정수, o로 표시된 칸의 번호

int arr[MAX][MAX];

long long cache[MAX][MAX];

 

//(x+1)+y*M -> 격자 안에 있는 숫자

long long path(int y, int x)

{

        //기저 사례

        if (y == N - 1 && x == M - 1) //목적지에 도달

               return 1;

        if (y >= N || x >= M) //범위 벗어날 경우

               return 0;

        long long &result = cache[y][x];

        if (result != -1)

               return result;

        result = 0;

        if ((x + 2) + y * M != K && (x + 1) + (y + 1)*M != K) //다음 움직일 칸이 K가 아닌 경우

        {

               if ((x + 2) + y * M < K && (x + 1) + (y + 1)*M < K) //오른쪽으로 움직이나 아래로 움직이나 K 미만인 경우

                       result += path(y + 1, x) + path(y, x + 1);

               else if ((x + 2) + y * M < K) //아래로 내려가면 K를 초과하는 경우

                       result += path(y, x + 1);

               else if ((x+2) + y * M > K && (x + 1) + (y + 1)*M > K) //이미 K를 지나간 경우

                       result += path(y + 1, x) + path(y, x + 1);

        }

        if ((x + 2) + y * M == K) //오른쪽이 K인 경우

        {

               result += path(y, x + 1);

        }

        if ((x + 1) + (y + 1)*M == K) //아래가 K인 경우

        {

               result += path(y + 1, x);

        }

        return result;

}

 

int main(void)

{

        cin >> N >> M >> K;

 

        int cnt = 1;

        for (int i = 0; i < N; i++)

               for (int j = 0; j < M; j++)

                       arr[i][j] = cnt++;

 

        memset(cache, -1, sizeof(cache));

        cout << path(0, 0) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~