[백준 1520] 내리막길 문제풀이

위 로고를 누르면 해당 문제로 이동합니다.

1차 풀이 (2018-07-05, 3948 KB, 4 MS)

 높이가 낮은 칸은 모두 탐색한다. 

왼쪽 위에서부터 오른쪽 아래로 이동하는 경로를 구하는 문제이지만,

그렇다고 모든 경로가 항상 오른쪽으로, 항상 아래쪽으로 향하지 않는다.

첫 번째 예시는 왼쪽선택을 포함한 최적 경로이고,

두 번째 예시는 위쪽선택을 포함한 최적 경로이다.

정리하자면 항상 오른쪽으로 항상 아래로 움직이려고 하지 말고,

가능한 모든 방향을 탐색해야 한다.

 루프는 없다. 

모든 방향을 탐색하다가 루프에 빠지면 어떻게 될까,

빙글빙글 돌다가 시간초과로 오답처리되는게 아닐까?

루프검출 로직을 넣어야 되는게 아닐까?

걱정말자, 루프는 발생하지 않는다.

루프가 만들어지려면 원 형태의 경로가 생성되어야 하는데,

원 형태의 경로가 만들어지려면 항상 내리막길로 움직이라는 제약에 위반된다.

즉, 항상 내리막길로 움직이라는 제약을 구현하면

루프는 발생하지 않는다.

 입력 사이즈가 꽤 크다? 

최대 가능한 입력횟수를 생각해보자,

맵이 500x500 이므로 최대 25만개 정도 들어올 수 있다.

최적화되지 않은 입력형태를 사용한다면,

입력에서 꽤 많은 시간을 잡아먹을 수 있다.

stdio 동기화를 해제한 cin 을 사용하자.

가장 빠른 방법은 아니지만, 4ms를 절약했다.

	#include <iostream>
	using namespace std;
	int M; // 지도의 세로 크기
	int N; // 지도의 가로 크기
	int map[501][501]; // 해당 지점의 높이.
	int dp [501][501]; // 해당 지점을 기준으로 할 때, 최적해의 수.
	int count(int x, int y)
	{
	if (dp[x][y] != -1) return dp[x][y];
	int dx[4] = { 0, 1, 0, -1 };
	int dy[4] = { 1, 0, -1, 0 };
	int ret = 0;
	for (int i = 0; i < 4; i++)
	{
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nx <= 0 || ny <= 0 || N < nx || M < ny) continue;
	if (map[nx][ny] < map[x][y])
	{
	if(dp[nx][ny] == -1) count(nx, ny);
	ret += dp[nx][ny];
	}
	}
	dp[x][y] = ret;
	return ret;
	}
	int main()
	{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> M >> N;
	for (int i = M; i > 0; i--)
	{
	for (int j = 1; j <= N; j++)
	{
	cin >> map[j][i];
	dp[j][i] = -1;
	}
	}
	dp[N][1] = 1;
	cout << count(1, M);
	}

view raw bj1520_1.cpp hosted with ❤ by GitHub