풀이
간단하게 점화식을 세우면
dp[i][j] = dp[i][j] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])라는 식이 나온다.
다시 생각해보자.
dp[i+1][j+1]을 굳이 갈 필요가 없다.
사탕의 개수가 음수가 아니기 때문에, dp[i+1][j] 또는 dp[i][j+1]을 거쳐서 dp[i+1][j+1]에 가는 값이
dp[i+1][j+1]로 바로 가는 값 보다 작아질 수 없다.
쉽게 말하자면 가로+세로(세로+가로)로 가는 값이 대각선으로 가는 값 보다 작아질 일이 없다는 것이다.
더 나가아서, dp 배열을 1차원으로 줄일 수 있다.
입력을 왼쪽위->오른쪽아래으로 받으면서 진행하게 되면
dp[j-1]은 dp[i][j-1]의 최댓값, dp[j]는 dp[i-1][j]의 최댓값이 된다.
따라서 dp[i] = current + max(dp[i-1], dp[i])라는 식을 세워 메모리 사용량을 줄일 수 있다.
코드
#include <stdio.h>
inline int max(int a, int b) { return a > b ? a : b; }
int i, j, n, m, k, dp[1001];
int main() {
scanf("%d %d", &n, &m);
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
scanf("%d", &k);
dp[j] = max(dp[j - 1], dp[j]) + k;
}
}
printf("%d", dp[m]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이