글 읽기 - dp 한번 봐주세요ㅠㅠ

hyundo1226 7년 전 0

메모제이션을 이용하여 시도는 해봤는데

계속 테스트케이스 출력은 4가 나오네요..

dp를 저렇게 짠게 맞는지 모르겠고..

어떻게 수정해야할까요?

#include<iostream>
using namespace std;
int m, n, cnt;
int arr[501][501];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int dp[501][501];
int move(int x, int y)
{
	for (int i = 0; i < 4; i++) { //4방향탐색으로 1칸이동
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (next_x < 0 || next_x >= m || next_y < 0 || next_y >= n)
			continue;
		dp[0][0] = 1; //0,0은 한가지의 가는방법이 존재
		if (arr[x][y] > arr[next_x][next_y]) { //만약 더 낮은곳으로 갈수있으면
			if (dp[x][y]) dp[next_x][next_y] +=dp[x][y];//그전까지경로를 계산했으면
                                                        //그 전경로를 더한 다음경로
			else {
				dp[next_x][next_y] = 1;        //없으면 처음가는길이니 1
				move(next_x, next_y);        //다시 움직여야 찾을 수있다
			}
		}
		if (next_x == m  && next_y == n ) {  
			
			return dp[x][y];
		}
	}
}
int main()
{
	freopen("Text.txt", "r", stdin);
	scanf("%d %d", &m, &n);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &arr[i][j]);

	printf("%d\n", move(0,0));
	return 0;
}

ljh6274 7년 전 5

아직 dp에 대해 잘 모르시는거 같습니다.

위의 방법 대로 제대로된 답이 나온다고 하여도 아마 시간초과를 받게 될 겁니다.

메모이제이션을 이용하면 이전에 구한 위치에 대한 답 예를들면 (0, 0)에서 (i, j)로 이동할때의 경우의 수가 dp[i][j]에 저장되어 있기 때문에 이를 재 호출하게 되면 앞의 과정을 반복 하는 것이 아니라 이미 구했기 때문에 반환만 하게 코드를 작성해야 합니다.

hyundo1226님께서 올려주신 코드를 약간 수정하여서 통과받은 코드를 아래에 추가해 드리겠습니다.

주석도 있으니 도움이 됐으면 좋겠습니다.

#include<iostream>
using namespace std;
int m, n, cnt;
int arr[501][501];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int dp[501][501];
int move(int x, int y)
{
	// 도착 지점
	if (x == m - 1 && y == n - 1)
		return 1;

	int &ret = dp[x][y];
	// 이미 구한 값이면 반환(메모이제이션)
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (next_x < 0 || next_x >= m || next_y < 0 || next_y >= n)
			continue;
		
		// 내려갈 수 있는 조건
		if (arr[x][y] > arr[next_x][next_y]) {
			// 도착점에 도착했으면 1이 반환 될 겁니다.
			ret += move(next_x, next_y);	
		}		
	}
	return ret;	
}
int main()
{
	scanf("%d %d", &m, &n);
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			// 갈 수 없는 길은 0이 될 수 있기 때문에
			// 한 번도 시도하지 않은 길을 -1로 초기화
			dp[i][j] = -1;
			scanf("%d", &arr[i][j]);			
		}
	}
	
	printf("%d\n", move(0, 0));
	return 0;
}

hyundo1226 7년 전 0

dp에대해서 조금은 더 이해가 됬습니다ㅠㅠ 감사합니다!

gomamon 7년 전 0

메모리제이션을 이해하는데 많은 도움이 되었습니다 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp 한번 봐주세요ㅠㅠ

hyundo1226 7년 전 0

ljh6274 7년 전 5

hyundo1226 7년 전 0

gomamon 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말