/<> 백준 2096번 : 내려가기 (C언어)

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

 

 

단순히 다이나믹 프로그래밍을 생으로 두 번 돌리니까 메모리 초과가 떴습니다. (항상 문제를 제대로 확인합시다)

슬라이딩 윈도우 알고리즘을 이용하면 해결됩니다. 코드 가독성도 좋던데, 진작에 이 알고리즘을 사용할걸 그랬습니다.

 

 

1. 최댓값을 저장하는 dp 배열과 최솟값을 저장하는 dp 배열을 저장합니다.

 

2. 이전 dp 값을 저장하는 pre_dp 배열을 생성합니다.

 

3. 다이나믹 프로그래밍을 이용하여 점수를 합합니다. 이 때 pre_dp 의 값을 비교하여 현재 dp 값을 구합니다.

 

4. 현재 dp 값을 구하면 pre_dp 값에 복사합니다.

 

 

<코드>

#include <stdio.h>

int num[100000][3];
int max_pre[3], max_cur[3];
int min_pre[3], min_cur[3];

int max2(int a, int b) {
    return a > b ? a : b;
}

int min2(int a, int b) {
    return a < b ? a : b;
}

int max3(int a, int b, int c) {
    int max = a;
    if(max < b) max = b;
    if(max < c) max = c;
    return max;
}

int min3(int a, int b, int c) {
    int min = a;
    if(min > b) min = b;
    if(min > c) min = c;
    return min;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d %d %d", &num[i][0], &num[i][1], &num[i][2]);

    max_pre[0] = num[0][0];
    max_pre[1] = num[0][1];
    max_pre[2] = num[0][2];
    
    min_pre[0] = num[0][0];
    min_pre[1] = num[0][1];
    min_pre[2] = num[0][2];

    for(int i = 1; i < n; i++) {
        max_cur[0] = max2(max_pre[0], max_pre[1]) + num[i][0];
        min_cur[0] = min2(min_pre[0], min_pre[1]) + num[i][0];
        
        max_cur[1] = max3(max_pre[0], max_pre[1], max_pre[2]) + num[i][1];
        min_cur[1] = min3(min_pre[0], min_pre[1], min_pre[2]) + num[i][1];
        
        max_cur[2] = max2(max_pre[1], max_pre[2]) + num[i][2];
        min_cur[2] = min2(min_pre[1], min_pre[2]) + num[i][2];
        
        for (int j = 0; j < 3; j++) {
            max_pre[j] = max_cur[j];
            min_pre[j] = min_cur[j];
        }
    }

    int max = max_pre[0], min = min_pre[0];
    for(int i = 1; i < 3; i++) {
        if(max < max_pre[i]) max = max_pre[i];    
        if(min > min_pre[i]) min = min_pre[i];
    }
    printf("%d %d\n", max, min);
    return 0;
}

 

 

(앞으로 코드를 작성할 때 main 함수를 최대한 간단하게 작성하는 연습을 해야겠습니다)