myt-algorithm-practice/Samsung SW Certi Adv
[Algorithm][C++] BOJ 11048 이동하기
hotamul
2021. 9. 8. 16:32
url: https://www.acmicpc.net/problem/11048
11048번: 이동하기
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는
www.acmicpc.net
풀이 핵심
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. 점화식 만들 때 거꾸로 생각해보기