(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍

"(백준/ 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; 
}