일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Django
- 알고리즘 문제
- 알고리즘 연습
- CSS
- DRF
- javascript
- Algorithm
- django widget
- react
- java
- PYTHON
- 알고리즘
- Git
- 알고리즘 풀이
- HTML
- API
- 파이썬
- 장고
- AWS
- js
- web
- django ORM
- MAC
- form
- django rest framework
- c++
- 파이썬 알고리즘
- Baekjoon
- es6
- 백준
Archives
- Today
- Total
수학과의 좌충우돌 프로그래밍
[C++] BAEKJOON 1890번 점프 본문
https://www.acmicpc.net/problem/1890
처음에는 bfs 나 dfs 를 생각하기 쉬운 문제지만 dp 를 사용해서 해결해야하는 문제입니다. dp 배열을 생성하여 각 원소는 해당 지점까지 올 수 있는 경로의 수를 저장하였습니다. 해당 칸에 써있는 수만큼 오른쪽과 아래쪽으로 이동하여 값을 갱신해주었습니다.
모든 칸을 전부 순회하지만 두 가지 경우에는 skip 을 해줄 수 있는데 마지막 지점에 도달했을 때 와 dp 배열이 0 일 때, 즉 해당 지점에 오는 경로가 하나도 없는 경우입니다.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int board[101][101];
long long dp[101][101] = {0,};
int N;
cin >> N;
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
cin >> board[i][j];
}
}
dp[0][0] = 1;
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
if (i==N-1 && j==N-1) continue;
if (!dp[i][j]) continue;
int jumpCount = board[i][j];
if (i+jumpCount < N)
dp[i+jumpCount][j]+= dp[i][j];
if (j+jumpCount < N)
dp[i][j+jumpCount]+= dp[i][j];
}
}
cout << dp[N-1][N-1] << "\n";
return 0;
}
문제 마지막을 보면,
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63-1보다 작거나 같다.
범위 조건 때문에 dp 배열을 long long
으로 선언해주었어야 했는데 이 부분을 놓쳐서 한참 찾았습니다. 범위에 항상 조심합시다!
'알고리즘 > C++' 카테고리의 다른 글
[C++] BAEKJOON 1509 팰린드롬 분할 (0) | 2019.09.06 |
---|---|
[C++] BAEKJOON 10942 팰린드롬? (0) | 2019.09.06 |
[C++] BAEKJOON 5052번 전화번호목록 (0) | 2019.08.26 |
[C++] BAEKJOON 8901번 화학제품(ACM-ICPC Daejeon 2011) (0) | 2019.08.02 |
[C++] BAEKJOON 8895번 막대배치(ACM-ICPC Daejeon 2012) (2) | 2019.07.31 |
Comments