Study hard
(c++)백준 1890번: 점프 본문
[풀이]
DP로 풀 수 있는 문제였다.
DP[i][j] : (1,1)에서 (i,j)까지 가는 경로의 수
점화식
if(i+Board[i][j]>N) : DP[i+Board[i][j]][j] = DP[i+Board[i][j]][j] + DP[i][j]
if(j+Board[i][j]>N) : DP[i][j+Board[i][j]] = DP[i][j+Board[i][j]] + DP[i][j]
#include <iostream>
#include <cstring>//memset
using namespace std;
int N;
int Board[101][101] = { 0, };
long long DP[101][101] = { 0, };
long long Range(int x, int y) {
if (x > N || y > N)
return 0;
else
return DP[x][y];
}
void solution() {
DP[1][1] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (DP[i][j] == 0 || (i == N && j == N))
continue;
if (i + Board[i][j] <= N)
DP[i + Board[i][j]][j] = DP[i + Board[i][j]][j] + DP[i][j];
if (j + Board[i][j] <= N)
DP[i][j + Board[i][j]] = DP[i][j + Board[i][j]] + DP[i][j];
}
}
cout << DP[N][N] << '\n';
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> Board[i][j];
}
}
solution();
return 0;
}
'백준 > DP' 카테고리의 다른 글
(c++)백준 5557번: 1학년 (0) | 2020.09.18 |
---|---|
(c++)백준 11049번: 행렬 곱셈 순서 (0) | 2020.09.16 |
(c++)백준 11058번: 크리보드 (0) | 2020.09.16 |
(c++)백준 2294번: 동전 2 (0) | 2020.09.16 |
(c++)백준 2293번: 동전 1 (0) | 2020.09.16 |