코드 복사/붙여넣기 하는 당신이 아름답습니다.

11048 : 이동하기

풀이

간단하게 점화식을 세우면

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-15 19:57

Read more posts by this author