Post

BOJ 2096 내려가기

Posted Updated
By noir1458
6 min read
BOJ 2096 내려가기

문제

N열 3행으로 숫자가 주어진다. 첫 줄에서 시작해서 마지막 줄까지 이동한다.
선택할때는 바로 아래, 그리고 아래와 붙어있는 숫자로만 이동이 가능하다.
이때 얻을 수 있는 최대, 최소 점수를 구하자.

접근법

비슷한 문제를 풀었기에 식은 바로 생각할 수 있었다

\[dp\_min[0] = v[0] + min(prev\_min[0],prev\_min[1])\] \[dp\_min[1] = v[1] + min(prev\_min[0],prev\_min[1],prev\_min[2])\] \[dp\_min[2] = v[2] + min(prev\_min[1],prev\_min[2])\]

그런데 이 문제는 메모리 제한이 4MB로 잡혀있다. 처음 제출 코드로 메모리 초과가 발생함.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

void print_v(vector<vector<int>> &v){
    for(const auto&e:v){
        for(const auto &e2:e){
            cout << e2 << " ";
        }
        cout << "\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int N; cin>>N;
    vector<vector<int>> v(N,vector<int>(3));

    for(int i=0;i<N;i++){
        for(int j=0;j<3;j++){
            cin >> v[i][j];
        }
    }
    vector<vector<int>> dp_min(N,vector<int>(3));
    vector<vector<int>> dp_max(N,vector<int>(3));
    
    for(int j=0;j<3;j++){
        dp_min[0][j] = v[0][j];
        dp_max[0][j] = v[0][j];
    }

    for(int i=1;i<N;i++){
        dp_min[i][0] = v[i][0] + min(dp_min[i-1][0],dp_min[i-1][1]);
        dp_min[i][1] = v[i][1] + min({dp_min[i-1][0],dp_min[i-1][1],dp_min[i-1][2]});
        dp_min[i][2] = v[i][2] + min(dp_min[i-1][1],dp_min[i-1][2]);

        dp_max[i][0] = v[i][0] + max(dp_max[i-1][0],dp_max[i-1][1]);
        dp_max[i][1] = v[i][1] + max({dp_max[i-1][0],dp_max[i-1][1],dp_max[i-1][2]});
        dp_max[i][2] = v[i][2] + max(dp_max[i-1][1],dp_max[i-1][2]);
    }

    cout << *max_element(dp_max[N-1].begin(),dp_max[N-1].end()) << " " << *min_element(dp_min[N-1].begin(),dp_min[N-1].end());
}

이게 처음 낸 코드인데 메모리 초과가 발생했다.

  1. 단순 계산
    • N열 3행 vector를 3개 사용했고, N의 최대치는 100,000
    • $ 4bytes \times 100000 \times 3 \times\ 3 \times = 3600000 bytes \approx 3.43 Mb $
    • 인데 제한 안에 들어오는것처럼 보이지만, 실제로는 vector의 오버헤드로 인해 통과하지 못한다.
  2. overhead
    • std::vector 라는 객체 하나는 내부적으로 데이터 시작주소, 끝주소, capacity를 관리하기 위해 약 24bytes 고유공간 차지
    • 이중 vector이므로 24bytes 백터 객체가 N개 생긴다
      • dp_min, dp_max, v 에서 각각 $ 100000행 \times 24bytes = 2.4 MB $
    • 최종 계산
      • 순수 데이터 : 3.43 MB
      • 백터 객체 오버헤드 : 2.4 * 3 = 7.2 MB
      • 총 10.63 MB 로 초과함.

메모리 제한을 볼때 1MB = int 형 배열 25만개, 4MB 제한이면 100만개가 넘으면 위험하다고 판단하도록 하자.
첫 코드에서 데이터가 90만개였고, vector오버헤드가 있으므로 무조건 MLE라고 판단이 가능함

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

void print_v(vector<vector<int>> &v){
    for(const auto&e:v){
        for(const auto &e2:e){
            cout << e2 << " ";
        }
        cout << "\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int N; cin>>N;
    vector<vector<int>> v(N,vector<int>(3));

    for(int i=0;i<N;i++){
        for(int j=0;j<3;j++){
            cin >> v[i][j];
        }
    }
    
    vector<int> prev_max(3);
    vector<int> dp_max(3);
    vector<int> prev_min(3);
    vector<int> dp_min(3);
    
    for(int j=0;j<3;j++){
        prev_min[j] = v[0][j];
        prev_max[j] = v[0][j];
    }

    for(int i=1;i<N;i++){
        dp_min[0] = v[i][0] + min(prev_min[0],prev_min[1]);
        dp_min[1] = v[i][1] + min({prev_min[0],prev_min[1],prev_min[2]});
        dp_min[2] = v[i][2] + min(prev_min[1],prev_min[2]);

        dp_max[0] = v[i][0] + max(prev_max[0],prev_max[1]);
        dp_max[1] = v[i][1] + max({prev_max[0],prev_max[1],prev_max[2]});
        dp_max[2] = v[i][2] + max(prev_max[1],prev_max[2]);

        for(int j=0;j<3;j++){
            prev_min[j]=dp_min[j];
            prev_max[j]=dp_max[j];
        }
    }

    cout << max({prev_max[0],prev_max[1],prev_max[2]}) << " " << min({prev_min[0],prev_min[1],prev_min[2]});
}

dp를 구할때 바로 전의 값만 요구하고 있으므로
여기에서 메모리를 더 줄일수가 있다.

메모리 초과 해결(슬라이딩 윈도우)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

void print_v(vector<vector<int>> &v){
    for(const auto&e:v){
        for(const auto &e2:e){
            cout << e2 << " ";
        }
        cout << "\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int N; cin>>N;

    vector<int> prev_max(3);
    vector<int> dp_max(3);
    vector<int> prev_min(3);
    vector<int> dp_min(3);
    vector<int> v(3);

    // 처음 부분 삽입
    int t;
    for(int j=0;j<3;j++){
        cin >> t;
        prev_min[j] = t;
        prev_max[j] = t;
    }
    N--;
    
    // N-1회 입력 받으면서 dp 계산
    while (N--)
    {
        for(int j=0;j<3;j++){
        cin >> t;
        v[j] = t;
        v[j] = t;
        }

        dp_min[0] = v[0] + min(prev_min[0],prev_min[1]);
        dp_min[1] = v[1] + min({prev_min[0],prev_min[1],prev_min[2]});
        dp_min[2] = v[2] + min(prev_min[1],prev_min[2]);

        dp_max[0] = v[0] + max(prev_max[0],prev_max[1]);
        dp_max[1] = v[1] + max({prev_max[0],prev_max[1],prev_max[2]});
        dp_max[2] = v[2] + max(prev_max[1],prev_max[2]);

        for(int j=0;j<3;j++){
            prev_min[j]=dp_min[j];
            prev_max[j]=dp_max[j];
        }
    }
    cout << max({prev_max[0],prev_max[1],prev_max[2]}) << " " << min({prev_min[0],prev_min[1],prev_min[2]});
}

toggling

이건 홀수일때 짝수일때 번갈아가면서 하면 되는건데.
용어를 듣자마자 어떤 느낌인지 알아서 코드를 더 수정하지는 않음.

1
2
3
4
5
6
7
8

int dp_max[2][3]; // 2개의 행만 사용

// i번째 줄 계산시
int curr = i%2;
int prev = (i-1) %2;

// 복사 과정 없이 접근가능
dp_max[curr][0] = v[0] + max(dp_max[prev][0], dp_max[prev][1]);
BOJ
BOJ DynamicProgramming SlidingWindow
This post is licensed under CC BY 4.0 by the author.