[Algorithm][C++] BOJ 11048 이동하기

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

11048번: 이동하기

 

풀이 핵심

1. 전형적 dynamic programing 문제

2. map[1001][1001], ans[1001][1001] 생성

3. 점화식 ans[r][c] = map[r][c] + max(map[r-1][c], map[r][c-1], map[r-1][c-1])

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int R, C;
int map[1001][1001];
int ans[1001][1001];

int get_max(int a, int b, int c) {
	return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

int main() {
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			ans[i][j] = map[i][j] + get_max(ans[i - 1][j], ans[i][j - 1], ans[i - 1][j - 1]);
		}
	}
	printf("%d", ans[R][C]);
	return 0;
}

 

아쉬운 점

1. DP 문제를 많이 접해보지 못해 dfs로 풀 생각만 했다

2. 시간 초과 나올 때는 DP 문제인지 생각하기

3. 점화식 만들 때 거꾸로 생각해보기