백준(BOJ) 11048번 이동하기

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

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

나의풀이 :

완전탐색의 경우 탐색했던 경로를 또 탐색해야 하니 시간초과가 되었고 따라서 각 부분 문제를 최적으로 풀고 

그 결과를 cache에 저장해 둠으로써 경로의 중복을 없앴다.

완전탐색

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX = 1000;

int map[MAX][MAX];

int N, M;

*/

int max(int a, int b, int c)

{

return a > b ? (a > c ? a : c) : (b > c ? b : c);

}

int findMax(int y, int x)

{

if (y > N - 1 || x > M - 1) return 0;

if (y == N - 1 && x == M - 1)

return map[y][x];

return max(findMax(y + 1, x + 1), findMax(y + 1, x), findMax(y, x + 1)) + map[y][x];

}

int main()

{

cin >> N >> M;

for (int i = 0; i < N; ++i)

for (int j = 0; j < M; ++j)

cin >> map[i][j];

int result = findMax(0, 0);

cout << result << endl;

return 0;

}

*/

다이나믹 프로그래밍

int max(int a, int b, int c)

{

return a > b ? (a > c ? a : c) : (b > c ? b : c); 

}

int findMax(int y, int x)

{

if (y > N - 1 || x > M - 1) return 0;

if (y == N - 1 && x == M - 1)

return map[y][x];

int& ret = cache[y][x];

if (ret != -1)

return ret;

return ret = max(findMax(y + 1, x + 1), findMax(y + 1, x), findMax(y, x + 1)) + map[y][x];

}

void Init()

{

for (int i = 0; i < N; ++i)

for (int j = 0; j < M; ++j)

cache[i][j] = -1;  // 캐쉬를 -1로 초기화

}

int main()

{

cin >> N >> M;

Init();

for (int i = 0; i < N; ++i)

for (int j = 0; j < M; ++j)

cin >> map[i][j];

int result = findMax(0, 0);

cout << result << endl;

return 0;

}