코딩공작소
[백준]점프 본문
https://www.acmicpc.net/problem/1890
1890번: 점프
문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로
www.acmicpc.net
2^63 - 1 흠 ... int로는 커버할 수 없다.
총 경로의 수.. 시간제한 1초.. bfs, dfs로는 시간초과가 난다고 한당.. DP로 하기로 생각했다.
(*long long타입은 %ld 로 출력)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
using namespace std;
int N;
long long map[100][100], DP[100][100];
void solve() {
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (map[i][j] == 0 || DP[i][j] == 0 || (i == N - 1 && j == N - 1)) continue;
int nr = i + map[i][j];
if (nr >= 0 && nr < N) DP[nr][j] += DP[i][j];
int nc = j + map[i][j];
if (nc >= 0 && nc < N) DP[i][nc] += DP[i][j];
}
printf("%ld\n", DP[N - 1][N - 1]);
}
int main() {
cin >> N;
for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) cin >> map[i][j];
DP[0][0] = 1;
solve();
}
|
cs |
'알고리즘 > DP' 카테고리의 다른 글
| [프로그래머스]정수삼각형 (0) | 2019.10.26 |
|---|---|
| [백준]내리막길 (0) | 2019.10.10 |
| DP,메모이제이션 (0) | 2019.10.10 |
| [SWEA]수영장 (0) | 2019.08.18 |
| [백준]퇴사(두번째 풂) (0) | 2019.07.11 |