[C언어] 백준 | 14430번 자원 캐기

https://www.acmicpc.net/problem/14430

14430번: 자원 캐기

안녕하세요.

제가 많이 풀어봤던 dp 종류의 문제입니다.

 

더했을 때 최고의 값만을 dp에 저장해주면서 배열을 진행해주면 쉽게 풀 수 있습니다.

if문을 쓴 것은 만약 i 나 j 가 0인데 배열상 -1을 시켜서 불러오려고 하면 배열에 오류가 생길 것 같아서 i와 j가 각각 0일 경우와 둘 다 0인 경우를 if문을 사용해서 나눠줬습니다.

 

하단에 if문을 쓰지 않았을 때 -1 배열을 참조하는 경우의 코드도 넣어놨으니 참고하시면 될 듯합니다.

 

질문은 댓글로 부탁드립니다.

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(void) {
    int n, m;
    int arr[301][301];
    int dp[301][301];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i != 0 && j != 0)
                dp[i][j] = MAX(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]);
            else if(i == 0 && j != 0) {
                dp[i][j] = dp[i][j - 1] + arr[i][j]; // 첫번째 행일 경우
            }
            else if(i != 0 && j == 0) {
                dp[i][j] = dp[i - 1][j] + arr[i][j]; // 첫번째 열일 경우
            }
            else if(i == 0 && j == 0) {
                dp[i][j] = dp[i][j] + arr[i][j]; //배열 [0][0]인 경우
            }

        }
    }
    printf("%d", dp[n - 1][m - 1]);
}

 

하단의 코드를 넣어봤더니 틀렸습니다 가 나왔습니다.

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(void) {
    int n, m;
    int arr[301][301];
    int dp[301][301];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
                dp[i][j] = MAX(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]);
        }
    }
    printf("%d", dp[n - 1][m - 1]);
}

dp[-1][0] 혹은 dp[0][-1] 혹은 dp[-1][-1] 등의 값을 비교할 수도 있는 경우.