문제 풀이

[c++] 백준 2096 내려가기

미분당한 적분상수 2023. 3. 8. 05:19

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

 

2096번: 내려가기

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

www.acmicpc.net

문제 특성상 메모리가 아주 제한되어있다.

dp값을 2차원 배열에 모두 저장하기에는 제한 조건을 초과하므로,

dp값을 계산하는 1차원 배열(dp_min, dp_max)과

dp값을 잠시 저장하는 1차원 배열(tmp)을

사용하여 재활용해가며 값을 구하자.

 

맞왜틀 당해서 지우고 다시 코드짜보니 ac받을 수 있었다.

#include<bits/stdc++.h>
using namespace std;
int arr[100100][3];
int tmp[3], dp_max[3], dp_min[3];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    //입력
    for(int i=0; i<n; i++)
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    //배열 초기값 설정
    tmp[0] = dp_max[0] = arr[0][0];
    tmp[1] = dp_max[1] = arr[0][1];
    tmp[2] = dp_max[2] = arr[0][2];
    /*
    점화식 돌리기
       1. [i][0]는 [i-1][0], [i-1][1]로부터 올 수 있다.
       2. [i][1]는 [i-1][0], [i-1][1], [i-1][2]로부터 올 수 있다.
       3. [i][2]는 [i-1][1], [i-1][2]로부터 올 수 있다.
    */
    //최댓값 구하기
    for(int i=1; i<n; i++){
        dp_max[0] = max(tmp[0], tmp[1]) + arr[i][0];
        dp_max[1] = max(tmp[0], max(tmp[1],tmp[2])) + arr[i][1];
        dp_max[2] = max(tmp[1], tmp[2]) + arr[i][2];
        tmp[0] = dp_max[0];
        tmp[1] = dp_max[1];
        tmp[2] = dp_max[2];
    }
    //최대값 출력
    cout << max(dp_max[0],max(dp_max[1],dp_max[2])) << ' ';
    //배열 초기값 설정
    tmp[0] = dp_min[0] = arr[0][0];
    tmp[1] = dp_min[1] = arr[0][1];
    tmp[2] = dp_min[2] = arr[0][2];
    //최솟값 구하기
    for(int i=1; i<n; i++){
        dp_min[0] = min(tmp[0], tmp[1]) + arr[i][0];
        dp_min[1] = min(tmp[0], min(tmp[1],tmp[2])) + arr[i][1];
        dp_min[2] = min(tmp[1], tmp[2]) + arr[i][2];
        tmp[0] = dp_min[0];
        tmp[1] = dp_min[1];
        tmp[2] = dp_min[2];
    }
    //최솟값 출력
    cout << min(dp_min[0],min(dp_min[1],dp_min[2]));
    return 0;
}

'문제 풀이' 카테고리의 다른 글

[c++] 백준 2138 전구와 스위치  (0) 2023.03.13
[c++] 백준 9251 LCS  (0) 2023.03.08
[c++] 백준 2294 동전 2  (0) 2023.03.07
[c++] 백준 13164 행복 유치원  (0) 2023.03.07
[c++] 백준 1041 주사위  (0) 2023.03.06