BOJ 1890 : 점프 - C++
점프
코드
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ll long long
using namespace std;
ll ans;
int N;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int board[105][105];
ll dp[105][105];
// dp[r][c] = r행 c열에서 N-1, N-1로 가는 경우의 수
ll DFS(int r, int c)
{
if(dp[r][c] != -1) return dp[r][c];
if(r == N-1 and c == N-1) return 1;
dp[r][c] = 0;
for(int d=0;d<2;d++)
{
int nr = r;
int nc = c;
int len = board[r][c];
if(len == 0) continue;
while(len--)
{
nr += dr[d];
nc += dc[d];
}
if(nr<0 or nc<0 or nr>=N or nc>=N) continue;
dp[r][c] += DFS(nr, nc);
}
return dp[r][c];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cin >> board[i][j];
for(int i=0;i<N;i++)
fill(dp[i], dp[i]+N, -1);
ans = DFS(0, 0);
cout << ans;
return 0;
}
- 문제 접근
DFS
를 통해 완전탐색
으로 경로 찾기 --> N이 100
이라서 너무커서 시간초과
가 확실
방향이 증가
밖에 없으니 vis없이 BFS를 수행
하면 모든 경로의 수
를 찾을 수 있을 것이라 생각
--> N이 작은 경우만 가능
/ N이 커지면 시간초과 발생
& 메모리초과 발생
--> BFS / DFS
를 방문체크(vis)없이 수행
하면 N에 따라 지수적으로 중복 방문
이 늘어나서 메모리 초과
가 난다
(BFS / DFS수행
시 특별한 조건이 없는 한
방문체크(vis)는 반드시 있어야 한다
는 것을 인지!)
해답
: DFS + DP
를 사용해서 풀어야 함!
- 주의
정답의 범위
가 2^63-1보다 작거나 같기 때문
에 long long 자료형
을 써야함 (DFS반환타입
도 꼭 바꾸자)
Author And Source
이 문제에 관하여(BOJ 1890 : 점프 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-1890-점프-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <deque> #include <numeric> #include <map> #include <stack> #define ll long long using namespace std; ll ans; int N; int dr[4] = {0, 1, 0, -1}; int dc[4] = {1, 0, -1, 0}; int board[105][105]; ll dp[105][105]; // dp[r][c] = r행 c열에서 N-1, N-1로 가는 경우의 수 ll DFS(int r, int c) { if(dp[r][c] != -1) return dp[r][c]; if(r == N-1 and c == N-1) return 1; dp[r][c] = 0; for(int d=0;d<2;d++) { int nr = r; int nc = c; int len = board[r][c]; if(len == 0) continue; while(len--) { nr += dr[d]; nc += dc[d]; } if(nr<0 or nc<0 or nr>=N or nc>=N) continue; dp[r][c] += DFS(nr, nc); } return dp[r][c]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin >> board[i][j]; for(int i=0;i<N;i++) fill(dp[i], dp[i]+N, -1); ans = DFS(0, 0); cout << ans; return 0; }
- 문제 접근
DFS
를 통해완전탐색
으로 경로 찾기 -->N이 100
이라서 너무커서시간초과
가 확실방향이 증가
밖에 없으니vis없이 BFS를 수행
하면모든 경로의 수
를 찾을 수 있을 것이라 생각
-->N이 작은 경우만 가능
/ N이 커지면시간초과 발생
&메모리초과 발생
-->BFS / DFS
를방문체크(vis)없이 수행
하면N에 따라 지수적으로 중복 방문
이 늘어나서메모리 초과
가 난다
(BFS / DFS수행
시특별한 조건이 없는 한
방문체크(vis)는 반드시 있어야 한다
는 것을 인지!)해답
:DFS + DP
를 사용해서 풀어야 함!
- 주의
정답의 범위
가2^63-1보다 작거나 같기 때문
에long long 자료형
을 써야함 (DFS반환타입
도 꼭 바꾸자)
Author And Source
이 문제에 관하여(BOJ 1890 : 점프 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-1890-점프-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)