[BOJ:11048]이동하기

www.acmicpc.net/problem/11048

11048번: 이동하기

코드

#include <stdio.h>
int candy[1001][1001];
int map[1001][1001];
int n, m;
int Bigger(int a, int b) {
    if (a > b)return a;
    else return b;
}
void Sol() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int result = Bigger(Bigger(candy[i - 1][j], candy[i][j - 1]), candy[i - 1][j - 1]);
            candy[i][j] = result + map[i][j];

        }
    }
    printf("%d\n", candy[n][m]);
}

int main() {
    freopen("input.txt", "rt", stdin);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d",&map[i][j]);
        }
    }
    Sol();

    return 0;
}

문제해결방법

• 처음에 문제를 읽고 DFS로 완전탐색을 하였다. 완전탐색으로 풀 경우 시간초과가 발생한다
• 각 경우의 최대 값을 구하는 방법은 (i,j)에 위치한 곳 까지의 최대 값은 (i-1,j), (i,j-1), (i-1,j-1)중에 최대값과 (i,j)의 사탕의 최대값을 합하면 (i,j)까지의 사탕의 최대값을 구할 수 있다.