백준 2096번 [내려가기](C++) -yes6686- 티스토리

백준 문제 풀이: 2096 [내려가기]

---

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

문제 설명:

크기가 n × 3인 게임판에서 맨 위 행부터 맨 아래 행까지 이동하며 각 칸의 점수를 획득할 때, 가능한 최댓값과 최솟값을 구하는 문제입니다.

이동 규칙은 다음과 같습니다:

• 현재 위치에서 바로 아래로 이동하거나, 바로 아래 왼쪽 또는 오른쪽 칸으로 이동할 수 있습니다.

입력:

• 첫째 줄에 게임판의 행 개수 n이 주어집니다. (1 ≤ n ≤ 100,000)
• 둘째 줄부터 n개의 줄에 각 행의 세 칸에 쓰인 점수가 주어집니다. 점수는 0 이상 9 이하의 정수입니다.

출력:

• 첫 번째 줄에 가능한 점수의 최댓값과 최솟값을 공백으로 구분하여 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int maxDp[3] = {0, 0, 0}; // 최댓값 계산용 DP
    int minDp[3] = {0, 0, 0}; // 최솟값 계산용 DP
    int tempMax[3], tempMin[3]; // 이전 행의 값을 임시로 저장할 배열

    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        // 최댓값 계산
        tempMax[0] = a + max(maxDp[0], maxDp[1]);
        tempMax[1] = b + max({maxDp[0], maxDp[1], maxDp[2]});
        tempMax[2] = c + max(maxDp[1], maxDp[2]);

        // 최솟값 계산
        tempMin[0] = a + min(minDp[0], minDp[1]);
        tempMin[1] = b + min({minDp[0], minDp[1], minDp[2]});
        tempMin[2] = c + min(minDp[1], minDp[2]);

        // 현재 행을 다음 행으로 복사
        for (int j = 0; j < 3; j++) {
            maxDp[j] = tempMax[j];
            minDp[j] = tempMin[j];
        }
    }

    // 결과 출력
    cout << *max_element(maxDp, maxDp + 3) << ' ' << *min_element(minDp, minDp + 3) << '\n';

    return 0;
}

예제

입력:
3
1 2 3
4 5 6
7 8 9

출력:
18 12

입력:
1
5 3 7

출력:
7 3

---

코드 설명

• 동적 프로그래밍: 현재 행에서 얻을 수 있는 최댓값과 최솟값을 계산합니다. 각 칸의 값은 바로 위 칸의 3가지 선택지 중 최댓값 또는 최솟값을 더해 계산됩니다.
• 공간 최적화: 이전 행의 결과만 필요하므로 배열 크기를 1행(3칸)으로 제한하여 메모리 사용량을 줄였습니다.

시간 복잡도

• 매 행마다 3칸을 처리하므로 시간 복잡도는 O(n)입니다.
• 최대 100,000개의 행도 효율적으로 처리할 수 있습니다.

---

결과

코드는 입력된 게임판에서 최댓값과 최솟값을 정확히 계산하며, 효율적인 동적 프로그래밍 방식을 사용하여 빠르게 결과를 도출합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!