[백준][11048] 이동하기

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

11048번: 이동하기

 

풀이과정

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));
}