# 백준 : 점프(1890)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1890_jump_DP)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

int             map[101][101];
long long int   DP[101][101];
int             size;

int main(void) {
    int value;
    int move;
    cin>>size;
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            cin>>value;
            map[i][j] = value;
        }
    }
    
    DP[0][0] = 1;
    for(int i=0; i<size; i++) {
        for(int j=0; j<size; j++) {
            move = map[i][j];
            
            // move right
            if((i != size - 1) && (i + move < size)) {
                DP[i + move][j] += DP[i][j];
            }
            if((j != size - 1) && (j + move < size)) {
                DP[i][j + move] += DP[i][j];
            }
        }
    }
    cout<<DP[size - 1][size - 1]<<endl;
    return 0;
}

풀이

세상에 이 문제 3시간동안 BFS로 풀어댓는데 결국 런타임 오류를 이기지 못했다.
도대체 왜 그런것일까 수없이 고민했지만 결국 답은 DP였다. 
나는 DP에 유독 약하다. 점화식을 세우는 방법이 아직 익숙치가 않아서, 이번에 좀 적응한 BFS를 이용하려고 했으나 이 또한 쉽지 않았다. 잘하는 분들의 말에 의하면 '중복 검색'을 제거하는 코드를 삽입해야 한다고 하는데, 그 부분에 대한 반례도 찾는게 쉽지 않았다.
어차피 DP도 공부해야 하기 때문에, 이번 기회에 DP 점화식 세우는 연습을 한다고 생각하고 이곳을 참고해서 코드 작성을 해보았다. 물론 내일 다시한번 내 힘으로 점화식을 세우고 코드를 작성하는 연습을 해봐야 할 것이다.
언제 DP를 사용하는게 효율적이고, 언제 BFS나 DFS를 사용하는게 효율적인지 잘 모르겠다. 이런 부분을 좀 연습해야 할 것 같다.
무튼 처음 시작점을 1로 두고, 그 지점에서부터 시작된 녀석들을 하나씩 증가해가면서 '나 여기 밟고 지나간다'는 표시를 해주는 것으로 점화식을 구성하면 된다. 그러면 마지막에 적힌 녀석은 답이 된다.
굉장히 간단하게 코딩할 수 있는데, DP는 코딩하는게 어려운게 아니라 식을 세우는게 어려운거니까..
연습! 연습! 계속 연습이 중요하다!