문제 링크 : https://www.acmicpc.net/problem/1520
문제 접근
- 위에서 아래로 가는 경로가 아닌, 왼쪽이나 오른쪽으로 가는 케이스를 어떻게 해결?
- 일반적 DP로는 불가능
- 백트래킹?
- 시작 위치에서 끝까지 가는 모든 경로를 확인
- 한 위치에서 갈수 있는 좌표는 크게 4가지
- 그럼 최악의 케이스 4^(MN) = 4^(2500) = 2^5000 >> 시간초과 >> 불가능
- 끝에서부터 시작하는 DP?
- 일반적으로 DP가 연산을 줄이기 위해서 시작점부터 진행하는데
- 각 정점에서 이전에 온것을 재활용
- DP[j][i] = (j,i) 좌표까지 올수 있는 경우의 수
- DP[j][i] = min(DP[j-1][i], DP[j+1][i], DP[j][i-1], DP[j][i+1])
- 단 현재 노드보다 계단 위치 높은 케이스에서만 진행
시간복잡도 계산
- O(MN) >> 2500
인트 계산
- 모든 입력 >> 10억 이하의정음수 >> INT 가능
- dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용
코드
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 43 44 45 46 47 48 49 50 51 | #include <iostream> using namespace std; typedef long long ll; int map[510][510]; ll dp[510][510]; int N,M; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; ll dfs(int y, int x) { if(dp[y][x] != -1) return dp[y][x]; dp[y][x] = 0; // 다음 노드 for(int k=0; k<4; k++) { int ny = y + dy[k]; int nx = x + dx[k]; if(ny>=0 && ny<N && nx>=0 && nx < M) { // 무한루프 생각해줄필요 없음 // 이전값과 비교해서 커야만 다음 재귀함수로 들어가기 때문에, 서로 왔다갔다 무한재귀할일은 없음 if(map[ny][nx] > map[y][x]) { dp[y][x] += dfs(ny, nx); } } } return dp[y][x]; } int main() { ios::sync_with_stdio(0); cin.tie(0); fill(&map[0][0], &map[509][510], 0); fill(&dp[0][0], &dp[509][510], -1); cin >> N >> M; for(int j=0; j<N; j++) { for(int i=0; i<M; i++) { cin >> map[j][i]; } } // 시작하는 경우 dp[0][0] = 1; cout << dfs(N-1, M-1) << '\n'; return 0; } | cs |
문제유형
- 끝에서부터 시작하는 DP
- DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
- 특히 2차원에서 상하좌우를 모두 고려해줘야할 때
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0) | 2021.02.06 |
|---|---|
| 백준 1963 소수 경로 (0) | 2021.02.06 |
| 백준 1309 동물원 쉬운 풀이(C++/CPP) (0) | 2021.02.06 |
| 백준 1890 점프 쉬운 풀이(C++/CPP) (0) | 2021.02.06 |
| 백준 2225 합분해 쉬운 풀이 (0) | 2021.02.06 |