백준 2096번 내려가기 (C++)

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

2096번: 내려가기

이 문제는 메모리 제한이 걸려있으므로, 무턱대로 100,000*3의 배열을 만들었다가는 메모리 초과가 나온다.

때문에 배열의 사이즈를 크게 잡지 않고 값을 입력받을 방법이 필요하다.

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수들을 설정하고, 첫 번째 줄의 값들을 저장한다.

    int n,a,b,c,x,y,z,maxi = 0, mini = 900001;
    cin >> n;
    cin >> a >> b >> c; // 첫 번째 행의 값들
    int arr[3] = {a,b,c}, arr2[3] = {a,b,c}; // 이전 행의 값들이 저장된 배열
    int samp[3] = {0,0,0}, samp2[3] = {0,0,0}; // 이전 행의 값들을 저장하기 위한 임시 배열

2. 아래 코드를 먼저 훑어보고 설명을 하나씩 일어나가보자.

    for(int i=2; i<=n; i++){ // 0
        cin >> x >> y >> z; // 1
        for(int i=0; i<3; i++){ // 2
            int temp = 0, temp2 = 0; // temp = max값 저장, temp2 = min값 저장
            if(i==0){ // 3
                temp = max(x+arr[0],x+arr[1]);
                temp2 = min(x+arr2[0],x+arr2[1]);
            }
            else if(i==1){ // 4
                temp = max(max(y+arr[0],y+arr[1]),y+arr[2]);
                temp2 = min(min(y+arr2[0],y+arr2[1]),y+arr2[2]);
            }
            else{ // 5
                temp = max(z+arr[1],z+arr[2]);
                temp2 = min(z+arr2[1],z+arr2[2]);
            }
            samp[i] = temp; // 6
            samp2[i] = temp2;
        }
        for(int i=0; i<3; i++){ // 7
            arr[i] = samp[i];
            arr2[i] = samp2[i];
        }
    }

(0) 두 번째 줄부터 n번째 줄까지 for문을 돌린다.

(1) 현재 행의 값들을 입력받아 저장한다.

(2) 열은 총 3개이므로, 0~2까지 for문을 돌린다.

(3) 0번째 열의 경우, 이전 값의 0열, 1열의 값만 받을 수 있다. 둘 중 max값과 min값을 더해서 각각 temp와 temp2에 저장한다.

이때 temp는 최대값을 저장하는 변수, temp2는 최소값을 저장하는 변수이다.

(4) 1번째 열의 경우, 이전 값의 0,1 그리고 2열 모두 접근이 가능하다. 때문에 세 가지 값중 max값과 min값을 더해서 각각 temp와 temp2에 저장한다.

(5) 2번째 열의 경우, 이전 값의 1열, 2열의 값만 받을 수 있다. 둘 중 max값과 min값을 더해서 각각 temp와 temp2에 저장한다.

(6) 그렇게 저장한 temp의 값은 samp배열에 저장해준다. 

(7) 이 부분이 중요하다. 위의 for문을 벗어나고, 여탯껏 저장한 samp의 배열들을 모두 arr와 arr2 배열에 저장한다. 이로써 n번째 줄까지 반복해서 이전 행열의 최대, 최소 값을 arr와 arr2배열에서 가져오거나 저장할 수 있다.

 

3. 최종적으로 n번째 행에서 최대값과 최소값을 출력한다.

    for(int i=0; i<3; i++){
        if(arr[i]>maxi) maxi = arr[i];
        if(arr2[i]<mini) mini = arr2[i];
    }
    cout << maxi << " " << mini << "\n";

 

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,a,b,c,a2,b2,c2,x,y,z,maxi = 0, mini = 900001;
    cin >> n;
    cin >> a >> b >> c;
    int arr[3] = {a,b,c}, arr2[3] = {a,b,c};
    int samp[3] = {0,0,0}, samp2[3] = {0,0,0};
    for(int i=2; i<=n; i++){
        cin >> x >> y >> z;
        for(int i=0; i<3; i++){
            int temp = 0, temp2 = 0;
            if(i==0){
                temp = max(x+arr[0],x+arr[1]);
                temp2 = min(x+arr2[0],x+arr2[1]);
            }
            else if(i==1){
                temp = max(max(y+arr[0],y+arr[1]),y+arr[2]);
                temp2 = min(min(y+arr2[0],y+arr2[1]),y+arr2[2]);
            }
            else{
                temp = max(z+arr[1],z+arr[2]);
                temp2 = min(z+arr2[1],z+arr2[2]);
            }
            samp[i] = temp;
            samp2[i] = temp2;
        }
        for(int i=0; i<3; i++){
            arr[i] = samp[i];
            arr2[i] = samp2[i];
        }
    }
    for(int i=0; i<3; i++){
        if(arr[i]>maxi) maxi = arr[i];
        if(arr2[i]<mini) mini = arr2[i];
    }
    cout << maxi << " " << mini << "\n";
    return 0;
}