[BOJ/C++] 2096: 내려가기

🏅 Gold 5

✏️ 1차 솔루션

1. 1열의 DP는 자기 자신을 저장
2. 2열부터
   0번째 숫자 ➡️ 앞 열의 0,1 번째 숫자 중 최대값, 최소값을 각각 DP에 저장
   1번째 숫자 ➡️ 앞 열의 0,1,2 번째 숫자 중 최대값, 최소값을 각각 DP에 저장
   2번째 숫자 ➡️ 앞 열의 2,3 번째 숫자 중 최대값, 최소값을 각각 DP에 저장
3. 마지막 열의 최대 DP 값 중 최대값, 최소 DP 값 중 최소값 각각 산출해서 결과 출력

🚨 1차 trouble

메모리 초과ㅠㅠ 아무래도 슬라이딩 윈도우 유형이기도 하고 최대값 저장 DP와 최소값 저장 DP를 둘 다 쓰면 메모리 사용을 많이 해야해서 그런듯

✏️ 최종 솔루션

⭐️ 슬라이딩 윈도우
DP로 최대값, 최소값을 계산하려면 최소 2열이 필요하기 때문에 슬라이딩 배열을 int mx[2][3] 으로 할당해서 이 배열을 옮겨가면서 최대값, 최소값 계산하기

• 어차피 DP로 풀이하기 때문에 최종적인 최대값, 최소값은 마지막 열에 모이므로 모든 값을 저장해줄 필요가 없음
• 현재 열의 최대값, 최소값을 계산한 이후에는 해당 열 각 숫자의 최대값, 최소값을 슬라이딩 배열의 앞 열(1열) 로 옮겨주기

📌 self feedback

DP를 사용하면 계속해서 필요한 값들을 저장해 나가기 때문에 모든 배열에 대한 값을 저장해둘 필요가 없음
➡️ 메모리 낭비가 심하다면 슬라이딩 윈도우를 떠올려볼 수 있음

✏️ 최종 code

#include <iostream>
using namespace std;

int main() {
    int board[100001][3];
    int mx[2][3];
    int mn[2][3];
    int n;
    cin >> n;
    
    for(int i=0;i<n;i++) {
        for(int j=0;j<3;j++) {
            cin >> board[i][j];
        }
    }
    
    // 1열의 최대값, 최소값을 board 1열 값으로 초기화
    for (int i=0; i<3; i++) {
        mx[0][i]=board[0][i];
        mn[0][i]=board[0][i];
    }

    for(int i=1;i<n;i++) {
        int x1=mx[0][0];
        int x2=mx[0][1];
        int x3=mx[0][2];
        
        mx[1][0]=max(x1,x2)+board[i][0];
        mx[1][1]=max(x1,max(x2,x3))+board[i][1];
        mx[1][2]=max(x2,x3)+board[i][2];
        
        int n1=mn[0][0];
        int n2=mn[0][1];
        int n3=mn[0][2];
        
        mn[1][0]=min(n1,n2)+board[i][0];
        mn[1][1]=min(n1,min(n2,n3))+board[i][1];
        mn[1][2]=min(n2,n3)+board[i][2];
        
        // 이번 열 최대값, 최소값 계산한 이후에는 앞 열로 위치 옮겨주기
        for (int j=0; j<3; j++) {
            mx[0][j]=mx[1][j];
            mn[0][j]=mn[1][j];
        }
    }

    int maxScore=max(mx[0][0],max(mx[0][1],mx[0][2]));
    int minScore=min(mn[0][0],min(mn[0][1],mn[0][2]));
    
    cout << maxScore << " " << minScore;
}