📃 coding test/◽ 백준
(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍
핑크코냥
2024. 7. 18. 17:23
728x90
"(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍"
이건 DP 중 어려운 문제에 속하는게 아닌거 같은데 잘못 생각해서 계속 틀렸다..
처음 생각했을 때 높은 곳에서 낮은 곳으로 이동한다고 해서 위로 ↑ 갈 수 없다고 생각했는데
높은 곳과 낮은 곳의 기준은 배열 안의 숫자지 배열의 위치를 따지는 것이 아니다.
그럼 즉 → 우 ↑ 위 ← 좌 ↓ 아래 모두 가능하다.
다른 사람들의 풀이를 보면 0, 0 부터 M-1, N-1까지 오는 경로에만 1을 리턴 해준다.
나는 거꾸로 생각했고, 목적지 부터 스타트 까지 갈 수 있는 방법으로 구현했다. 사실 상 같다.
그리고 나처럼(?) 바보같이 모든 if문을 나누지 말고.. for문을 이용하자.
다른 사람들의 문제 풀이를 보면 좌,우,상,하 모두 지정해두고 했지만 난 더하고 뺐다 직접 ^^;;
int dy[4]={0,0,-1,1};
int dx[4]={-1,1,0,0};
#include <iostream>
#include <limits>
#include <algorithm>
using namespace std;
int gMatrix[501][501];
int m_row, m_col;
bool visit[501][501] = {false, };
int dp[501][501];
int Func(int x, int y)
{
if (y >= m_col || x >= m_row ||y < 0 || x < 0)
return 0;
if (x == 0 && y == 0)
{
return 1;
}
if (visit[x][y])
return dp[x][y];
visit[x][y] = true;
if (gMatrix[x][y] < gMatrix[x][y - 1])
{
dp[x][y] = dp[x][y] + Func(x, y - 1);
}
if (gMatrix[x][y] < gMatrix[x - 1][y])
{
dp[x][y] = dp[x][y] + Func(x - 1, y);
}
if (gMatrix[x][y] < gMatrix[x][y + 1])
{
dp[x][y] = dp[x][y] + Func(x, y+1);
}
if (gMatrix[x][y] < gMatrix[x + 1][y])
{
dp[x][y] = dp[x][y] + Func(x + 1, y);
}
return dp[x][y];
}
int main(void)
{
cin >> m_row >> m_col;
for (int i = 0; i < m_row; ++i)
{
for (int j = 0; j < m_col; ++j)
{
cin >> gMatrix[i][j];
}
}
cout << Func(m_row-1, m_col-1);
//cout << gCount;
return 0;
}
728x90