'알고리즘' 카테고리의 다른 글
| [DP] 백준 1932 숫자삼각형 (0) | 2018.04.29 |
|---|---|
| [DP] 백준 14501 퇴사 (0) | 2018.04.29 |
| [DP] 백준 9251 LCS (0) | 2018.04.29 |
| [DP] 백준 10942 팰린드롬? (0) | 2018.04.29 |
| [DP] 백준 1890 점프, 3372 보드 점프 다시풀만한 것 (0) | 2018.04.29 |
[DP] 백준 1520 내리막길
2018. 4. 29. 00:33
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <string>
using namespace std;
int arr[501][501];
int n, m, cnt = 0;
bool visit[501][501];
int aa = 0;
void go(int x, int y,int before) {
if (x == n - 1 && y == m - 1) {
cnt++;
return;
}
if (before <= arr[x][y]) {
return;
}
if (x > n - 1 || y > m - 1 || y<0) {
return;
}
/*if (aa == 10) { 경로확인용 test 코드
aa = 0;
cout << endl;
}
cout << arr[x][y] << ' ';
aa++;*/
go(x + 1, y, arr[x][y]);
go(x, y+1, arr[x][y]);
go(x, y-1, arr[x][y]);
go(x - 1, y, arr[x][y]);
}
int main(void)
{
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[i][j];
}
}
go(0,0,INT_MAX);
cout << cnt << endl;
return 0;
}
완전탐색으로 구현 => 시간초과
Memoization 을 어떻게 해야할 지 모르겠다.
dfs로
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <string>
using namespace std;
int arr[501][501];
int n, m, cnt = 0;
int d[501][501];
int aa = 0;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int go(int x, int y) {
if (x == n - 1 && y == m - 1) {
return 1;
}
if (d[x][y] != -1) {
return d[x][y];
}
int& ans = d[x][y]+=1;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (arr[nx][ny] < arr[x][y]) {
ans += go(nx, ny);
}
}
}
return ans;
}
int main(void)
{
memset(d, -1, sizeof(d));
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[i][j];
}
}
cout << go(0, 0) << endl;
return 0;
}