백준 1520. 내리막 길 - 문제풀이 (c++) (dfs, dp)

🔎 1520. 문제 보기

https://www.acmicpc.net/problem/1520

💡 문제 풀기 전

이 2가지의 상황에서 20을 중복으로 지나게 되는데, 이 부분을 방문 예외처리를 어떻게 할 지 고민을 많이 했다. 근데 생각해보니 다음 숫자는 항상 지금 숫자보다 작은 숫자로만 가기 때문에 방문체크를 따로 하지 않아도 된다.

📝 코드 보기

시간초과 코드

#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[555][555];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
int answer=0;

int solve(int y, int x) {
	if(y==n-1 && x==m-1) return 1;
	
	for(int i=0; i<4; i++) {
		int ny=y+dy[i];
		int nx=x+dx[i];
		
		if(ny<0 || nx<0 || ny>n-1 || nx>m-1) continue;
		if(a[y][x]>a[ny][nx]) {
			answer+=solve(ny, nx);
		}
	}
	
	return 0;
}

int main() {
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> a[i][j];
		}
	}
	
	solve(0, 0);
	cout << answer;	
	return 0;
} 

정답 코드

#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[555][555];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
int dp[555][555];
int answer=0;

int solve(int y, int x) {
	if(y==n-1 && x==m-1) return 1;
	int &ret=dp[y][x];
	if(ret!=-1) return ret;
	ret=0;
	
	for(int i=0; i<4; i++) {
		int ny=y+dy[i];
		int nx=x+dx[i];		
		if(ny<0 || nx<0 || ny>n-1 || nx>m-1) continue;
		if(a[y][x]>a[ny][nx]) {
			ret+=solve(ny, nx);
		}
	}
	
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> a[i][j];
		}
	}

	memset(dp, -1, sizeof(dp));
	solve(0, 0);
	cout << dp[0][0];	
	return 0;
} 

🎈 코드 풀이 및 관련 개념

처음에는 dfs를 통해서 구현했는데 시간초과가 발생했다.
=> 당연하다. 방문체크를 하지 않고 현재칸보다 다음칸의 숫자가 작으면 되는데로 dfs탐색했기 때문에

그래서 dp를 이용해서 방문체크(메모이제이션)를 했다.