백준 1890 점프 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1890

문제 접근

• 이전의 경우의 수가 다음것에 바로 사용됨 >> DP
• DP
  • 3이라고 적혀있는 칸일경우, 3칸 오른쪽이나 아래쪽에 값을 반영 가능할까? >> 가능할것 같음
  • DP[Y][X] = Y,X칸을 갈 수 있는 경우의 수
  • DP[0][0] = 1; , DP[0][0]의 값이 K일경우
  • DP[K][0] += DP[0][0], DP[0][K] += DP[0][0]

시간복잡도 계산

• 가로 * 세로 >> O(N^2) >> 1e4

인트 계산

• 모두 갈수 있는 경우라면 >> 2^100 >> 1e30 >> 인트 초과 >> DP값은 long long 사용

코드

#include <iostream>
 
using namespace std;
typedef long long ll;
 
ll dp[110][110];
int map[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            cin >> map[j][i];
        }
    }
    
    fill(&dp[0][0], &dp[109][110], 0);
    dp[0][0] = 1;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            int k = map[j][i];
            if(k==0) continue;
            dp[j+k][i] += dp[j][i];
            dp[j][i+k] += dp[j][i];
        }
    }
    
    cout << dp[N-1][N-1]<< '\n';
    
    return 0;
}
 

문제유형

• 일반 DP