[백준][11048] 이동하기

Algorithm/백준

[백준][11048] 이동하기

1일1코딩 2020. 3. 22. 22:57

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

11048번: 이동하기

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으

www.acmicpc.net

풀이과정

1. dp로 접근했다.

2. dp[n][m]에는 최대 사탕 갯수가 들어간다.

3. dp[n][m] = max(dp[n-1][m] , dp[n][m -1]) 라는 식을 구하였다.

소스코드

#include <stdio.h>
#include <string.h>

int map[1001][1001];
int dp[1001][1001];
int N, M;


int solution(int y, int x)
{
	if (dp[y][x] != -1) {
		return dp[y][x];
	}
	
	if (y - 1 >= 0) {
		dp[y][x] = solution(y - 1, x);
	}
	if (x - 1 >= 0) {
		int tmp = solution(y, x - 1);
		if (tmp > dp[y][x]) {
			dp[y][x] = tmp;
		}
	}
	dp[y][x] += +map[y][x];
	return dp[y][x];
}
int main()
{
	
	scanf("%d %d", &N, &M);
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	dp[0][0] = map[0][0];
	printf("%d\n", solution(N, M));
}