[백준/Baekjoon] 2096 내려가기 C++ :: Dynamic Programming

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

2096번: 내려가기

---

1. Logic

해당 문제는 메모리 제한이 4MB로 굉장히 작으므로 배열의 수를 최대한 줄이는 데 초점을 두고 풀이해야한다.

 

간단한 설명은 입력받은 수를 변수에 저장한 후 입력받은 수를 기준으로 위의 수를 서로 비교하여 크고 작은 수를 가져와서 현재의 배열에 저장하는 식으로 풀이한다.

 

코드를 보면 더 잘 이해가 갈 것이다.

 

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n;

int arr[3];
int maxVal[3];
int minVal[3];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;

    cin >> arr[0] >> arr[1] >> arr[2];

    //초기화
    for (int i = 0; i < 3; i++) {
        maxVal[i] = minVal[i] = arr[i];
    }

    for (int i = 1; i < n; i++) {
        int n1, n2, n3;
        cin >> n1 >> n2 >> n3;

        int tempMax0 = maxVal[0];
        int tempMax1 = maxVal[1];
        int tempMax2 = maxVal[2];

        maxVal[0] = max(tempMax0, tempMax1) + n1;
        maxVal[1] = max(max(tempMax0, tempMax1), tempMax2) + n2;
        maxVal[2] = max(tempMax1, tempMax2) + n3;

        int tempMin0 = minVal[0];
        int tempMin1 = minVal[1];
        int tempMin2 = minVal[2];

        minVal[0] = min(tempMin0, tempMin1) + n1;
        minVal[1] = min(min(tempMin0, tempMin1), tempMin2) + n2;
        minVal[2] = min(tempMin1, tempMin2) + n3;
    }

    cout << max(max(maxVal[0], maxVal[1]), maxVal[2]) << ' ';
    cout << min(min(minVal[0], minVal[1]), minVal[2]);
}

---

3. Feedback

- 처음에는 DP문제인 줄 시간복잡도와 메모리를 계산해 보니( 4 × 1000000 = 4000000 = 4MB) 비슷하게 딱 맞아떨어져서 기본 DP템플릿을 놓고 풀었지만 메모리 초과가 났다. 알고리즘 분류를 보니 슬라이딩 윈도우라는데,, 슬라이딩 윈도우에 대해 알아봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐