백준 1890 점프
https://www.acmicpc.net/problem/1890
-
다이나믹 프로그래밍
-
풀이
- dp 배열과 정답 배열 두개를 만들고, dp 배열에서 오른쪽과 아래로 이동했을 때, 숫자가 N보다 크지 않으면 정답 배열에 경우의 수 합을 넣는다.
(arr[i+d[i][j]][j]+=ans[i][j]) - 마지막 (N,N)칸에서 한번 더 경우의 수들을 더해주지 않도록 한다.
if .... !(i==N and j==N) - 값이 int보다 커질 수 있으므로 long long 자료형을 사용한다.
- 코드
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
ll N;
ll d[101][101], ans[101][101];
int main(void){
fast;
cin>>N;
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
cin>>d[i][j];
}
}
memset(ans,0,sizeof(ans));
ans[1][1]=1;
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
if(i+d[i][j]<=N and ans[i][j] and !(i==N and j==N)) ans[i+d[i][j]][j]+=ans[i][j];
if(j+d[i][j]<=N and ans[i][j] and !(i==N and j==N)) ans[i][j+d[i][j]]+=ans[i][j];
}
}
cout<<ans[N][N];
}
Author And Source
이 문제에 관하여(백준 1890 점프), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@y-siro/백준-1890-점프저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)