[1520] 내리막 길, c++

[1520] 내리막 길

www.acmicpc.net/problem/1520

1520번: 내리막 길

한줄 후기 : 난 오마이걸이 제일 좋아

 

지혜가 풀어보고 싶다해서 시작

정답률 ^^,, 지혜는 항상 어려운 문제만 고른다~

//AC 
#include <iostream>
using namespace std;
int n,m;
int arr[501][501];
long long dp[501][501];
long long way(int i, int j){
	if(i == (n-1) && j ==(m-1)){
		return 1;
	}
	if(dp[i][j] != -1){
		return dp[i][j];
	}
	dp[i][j] = 0;
	if(arr[i+1][j] < arr[i][j] && i+1 < n){
		dp[i][j] += way(i+1,j);	
	}
	if(arr[i-1][j] < arr[i][j] && i-1 >= 0){
		dp[i][j] += way(i-1, j);		
	}
	if(arr[i][j+1]<arr[i][j] && j+1 < m){
		dp[i][j] += way(i,j+1);
	}
	if(arr[i][j-1] <arr[i][j] && j-1 >= 0){
		dp[i][j] += way(i,j-1);
	}
	return dp[i][j];
}
int main(){
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d", &arr[i][j]);
			dp[i][j] = -1;
		}
	}
	cout << way(0,0);
}

처음에 보자마자 아 이거 재귀 쓸 거 같은데 라고 생각하고 조금 화났다 ^^

나는 재귀를 못하거든

일단 높이 입력받을 이차원 배열, dp 배열도 이차원으로 해야할 것 같았음.

way 함수를 만들었는데, 매개변수 i,j 는 각 각 현재의 위치이다. 즉, 경로를 찾는 것은 동일한 경로로 가던 중 현재 값보다 작은 높이가 상,하,좌,우에 있다면 경로가 달라지는 것이므로 재귀 함수를 통해 달라질 때마다 그 위치로 새로 재귀를 돌리자 라는 게 내가 생각한 풀이

​

BUT,,,

시간 초과 ^^

시간 초과 났던 코드 보여드림

//시간 초과
#include <iostream>
#include <string.h>
using namespace std;
int n,m;
int arr[501][501];
long long dp[501][501];
long long cnt=0;
void way(int i, int j){
	if(i == (n-1) && j ==(m-1)){
		return;
	}
	dp[i][j] =1;
	if(arr[i+1][j] < arr[i][j] && i+1 < n){
		dp[i+1][j] += dp[i][j];	
		way(i+1,j);
	}
	if(arr[i-1][j] < arr[i][j] && i-1 >= 0){
		dp[i-1][j] += dp[i][j];
		way(i-1, j);		
	}
	if(arr[i][j+1]<arr[i][j] && j+1 < m){
		dp[i][j+1] += dp[i][j];
		way(i,j+1);
	}
	if(arr[i][j-1] <arr[i][j] && j-1 >= 0){
		dp[i][j-1] += dp[i][j];
		way(i,j-1);
	}
}
int main(){
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d", &arr[i][j]);
			dp[i][j] = 0;
		}
	}
	dp[0][0] = 1;
	way(0,0);
	cout << dp[n-1][m-1];
}

재귀가 아닌가? 라 생각 했는데 아무리 생각해도 재귀 말고 반복문으로는 못 할 것 같았음 ㅋ..

생각만 하다 걍 질문 코너에서 나랑 비슷한 문제로 질문 한 사람들 걸 봤는데 wow

dp 배열을 -1로 초기화 하고 현재 위치를 처음 방문 한 건지, 이미 방문 했던 건지 구분해 줘야 한다 했다.

즉, dp를 처음에 0으로 초기화하면 그 값이 처음 방문해서 0인건지, 아니면 경로가 없어서 0인건지 구분 할 수 없어 경로가 없는 위치도 계속 연산을 수행해 쓸데 없는 시간 초과가 나는 거였다.

​

if(i == (n-1) && j ==(m-1)){
	return 1;
}

이 부분이 재귀를 돌고 돌아 오른쪽 아래에 도착 했을 경우 => 경로 1개

반환해준 경로 1개를 dp[i][j] 에 더해주는 형식

if(dp[i][j] != -1){
	return dp[i][j];
}

만약 한번 방문 했었던 곳 or 경로가 없는 곳이라면 이미 알고 있는 dp[i][j] 반환

조건문 연산 수행후 return dp[i][j]; 를 통해 모든 경로의 수를 반환하면 된다.

주의 할 점-> 경로가 10억 이하라 했느니까 자료형은 long이나 long long 으로 합시다.