반응형
https://www.acmicpc.net/problem/1890
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장
www.acmicpc.net
[ 문제풀이 ]
1. 재귀 함수를 통해서 각 좌표에서 갈 수 있는 좌표의 경로 개수를 모두 더해줍니다.
2. 정답의 범위가 int형을 벗어나므로 long long 자료형을 사용해줍니다.
3. 마지막에 dfs(0, 0)을 출력해줍니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include<iostream> using namespace std; int N; int arr[100][100]; int dy[2] = { 0,1 }; int dx[2] = { 1,0 }; long long dp[100][100]; long long dfs(int y, int x) { if (dp[y][x] != 0) return dp[y][x]; if (arr[y][x] == 0 && y != N - 1 && x != N - 1) { return 0; } if (y == N - 1 && x == N - 1) return 1; for (int i = 0; i < 2; i++) { int yy = y + dy[i]*arr[y][x]; int xx = x + dx[i]*arr[y][x]; if (yy >= 0 && yy < N && xx >= 0 && xx < N) { dp[y][x] += dfs(yy, xx); } } return dp[y][x]; } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &arr[i][j]); } } printf("%lld", dfs(0,0)); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1309번 - 동물원 (C++) (0) | 2022.10.30 |
|---|---|
| [ 백준 ] 1965번 - 상자넣기 (C++) (0) | 2022.10.29 |
| [ 백준 ] 9461번 - 파도반 수열 (C++) (0) | 2022.10.27 |
| [ 백준 ] 2579번 - 계단 오르기 (C++) (0) | 2022.10.26 |
| [ 백준 ] 2410번 - 2의 멱수의 합 (C++) (0) | 2022.10.25 |