[2096] 내려가기

문제 링크 : https://www.acmicpc.net/problem/2096

2096 - 내려가기

본문

$N$줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 $N$($1 \leq N \leq 100\,000$)이 주어진다. 다음 $N$개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

제한

시간 제한	메모리 제한
1sec	4MB

---

풀이

간단한 dp문제이다. 규칙이 바뀌는 지점도 없고 규칙 자체도 간단하다. 바로 아래와 그 옆만 비교해서 최댓값, 최솟값을 계속해서 이어가기만 하면 된다.

하지만 가장 치명적인 조건이 하나 있다. 메모리 조건이 4MB라는 것. 기존의 dp처럼 모든 칸을 만들어서 저장한다면 메모리 제한에 걸린다. 결국 dp의 모든 칸을 저장할 수 없으니 칸을 줄여야한다는 것을 의미하게 된다.

생각해보면 문제에서 dp를 사용하는 이유는 이전 결과값을 이용하기 위해서다. 그런데 그 이전 결과값을 사용하는 범위가 어떻게 될까? $i$번째 칸을 지나게 될 때, 사용하는 결과는 $i-1$번째 결과만을 사용한다. 지금까지 결과만 잘 계산했었다면 이전의 결과는 아예 필요가 없는 것. 즉, 최근 1번의 결과만 기록하고 있다면 이전 기록은 의미가 없다는 것을 의미한다. 이것을 슬라이딩 윈도우 기법이라고 하기도 하는데, 자세한건 참고쪽을 보도록 하자.

• 참고 알고리즘 : 다이나믹 프로그래밍, 슬라이딩 윈도우

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 21

#include <stdio.h>

typedef struct Node {
    int minV;
    int maxV;
} ND;

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) > (b)) ? (b) : (a))
int main() {
    ND ret[3];
    int n;
    scanf("%d", &n);

    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    ret[0] = (ND){a, a}, ret[1] = (ND){b, b}, ret[2] = (ND){c, c};

    ND temp[3];
    for (int i = 1; i < n; ++i) {
        scanf("%d %d %d", &a, &b, &c);

        temp[0] = (ND){min(ret[0].minV, ret[1].minV) + a, max(ret[0].maxV, ret[1].maxV) + a};
        temp[1] = (ND){min(min(ret[0].minV, ret[1].minV), ret[2].minV) + b, max(max(ret[0].maxV, ret[1].maxV), ret[2].maxV) + b};
        temp[2] = (ND){min(ret[1].minV, ret[2].minV) + c, max(ret[1].maxV, ret[2].maxV) + c};

        ret[0] = temp[0], ret[1] = temp[1], ret[2] = temp[2];
    }

    printf("%d %d", max(max(ret[0].maxV, ret[1].maxV), ret[2].maxV), min(min(ret[0].minV, ret[1].minV), ret[2].minV));
    return 0;
}