[1890번] 점프

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

처음에는 bfs로 구상하였는데 최악의 경우를 고려하지 않아 메모리 초과를 받게 되었다.

이 문제는 DP로 해결할 수 있는 문제이고, 

[14430번] 자원캐기 :: http://www.crocus.co.kr/588 문제를 응용하면 해결할 수 있다.

조건문 내에 i != n-1의 의미는 마지막 행렬의 값이 0이다 보니 next가 0이 되어 자기 자신을 더하는 것을 막기 위함이다.

소스 코드 : 

<< DP를 이용하여 AC를 받은 코드 >>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   int map[101][101]; long long int DP[101][101];   int main() {     int n;       scanf("%d", &n);     for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             scanf("%d", &map[i][j]);       DP[0][0] = 1;       for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             int next = map[i][j];               if (i != n - 1 && i + next < n)                 DP[i + next][j] += DP[i][j];               if (j != n - 1 && j + next < n)                 DP[i][j + next] += DP[i][j];           }     }       printf("%lld", DP[n - 1][n - 1]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

<< BFS를 이용하여 FAIL(메모리 초과)을 받은 코드 >>

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
int map[101][101];
long long int DP[101][101];
 
typedef pair<int, int> pii;
 
queue<pii> q;
 
int main()
{
    int n;
    long long int cnt = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &map[i][j]);
 
    DP[0][0] = 0;
    q.push(pii(0, 0));
 
    while (!q.empty())
    {
        pii here = q.front();
        q.pop();
        int y = here.first;
        int x = here.second;
        //cout << "x :: " << x << " y :: " << y << endl;
        if (y == n - 1 && x == n - 1)
        {
            cnt++;
            continue;
        }
        int next = map[y][x];
 
        if (y + next < n)
            q.push(pii(y + next, x));
 
        if (x + next < n)
            q.push(pii(y, x + next));
    }
 
    printf("%lld", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>