[BOJ] 2096 내려가기

1. 문제 링크

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

2. 해설

이 문제는 간단한 트릭을 사용하는 dp 문제이다. 평소에 dp 문제를 푸는 식으로 문제를 풀게 되면 14MB의 작은 메모리 공간에 메모리 초과라는 결과를 맞게 된다. 간단하게 메모리를 재사용하면 답을 구할 수 있다.

1. 첫 줄을 받고 int dp[3][3] 이라는 배열에 대입한다.

2. 2번째 줄부터는 2차원 dp 배열의 0번째 줄의 값들 중 가능한 최대와 최소를 구해서 1번째 줄에 대입한다.

3. 다시 1번째 줄을 0번째 줄에 대입하고 반복한다.

3. 소스코드

#include<iostream>
#include<algorithm>
#include<string>
#define fio ios_base::sync_with_stdio(0), cin.tie(0)
#define MAXNUM 100100
using namespace std;

struct temp{
    int x, n;
};

int main(){
    int n;
    temp dp[2][3];
    int map[3]={0};
    scanf("%d", &n);
    for (int i=0; i<3; i++) {
        scanf("%d", &map[i]);
        dp[0][i].x = map[i]; dp[0][i].n = map[i];
    }
    
    for (int i=1; i<n; i++) {
        for (int j=0; j<3; j++) {
            scanf("%d", &map[j]);
        }
        
        dp[1][0].n = min(dp[0][0].n, dp[0][1].n) + map[0];
        dp[1][0].x = max(dp[0][0].x, dp[0][1].x) + map[0];
        
        dp[1][1].n = min({dp[0][0].n, dp[0][1].n, dp[0][2].n}) + map[1];
        dp[1][1].x = max({dp[0][0].x, dp[0][1].x, dp[0][2].x}) + map[1];
        
        dp[1][2].n = min(dp[0][1].n, dp[0][2].n) + map[2];
        dp[1][2].x = max(dp[0][1].x, dp[0][2].x) + map[2];
        
        for (int j=0; j<3; j++) {
            dp[0][j] = dp[1][j];
        }
    }
    
    printf("%d %d\n", max({dp[0][0].x, dp[0][1].x, dp[0][2].x}), min({dp[0][0].n, dp[0][1].n, dp[0][2].n}));
    
    return 0;
}

4. 추가 언급

우리는 algorithm 헤더파일에 있는 min과 max 함수를 알고 있다. 그런데, 3개 이상의 값들 중에 가장 큰 값을 찾으려면 어떻게 해야할까? 간단한 방법으로는 max안에 max함수를 넣어서 구하는 방법이 있겠다.

max(a, max(b, c));

아래의 코드를 보면 위와 같이 구하지 않았다. 어떻게 이게 되는 것일까?

dp[1][1].n = min({dp[0][0].n, dp[0][1].n, dp[0][2].n}) + map[1];
dp[1][1].x = max({dp[0][0].x, dp[0][1].x, dp[0][2].x}) + map[1];

실제로 30줄의 max와 min 함수에 들어가서 코드를 보면 max_element와 min_element로 되어있다. 각각의 함수는 원하는 범위에서 가장 큰 값과 가장 작은 포인터(이터레이터)를 얻어 오는 함수이다. max코드는 아래와 같이 구현되어 있다. 물론 min도 이렇게 되어있다.

template<class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_Tp
max(initializer_list<_Tp> __t)
{
    return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
}

template <class _ForwardIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
_ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
    if (__first != __last)
    {
        _ForwardIterator __i = __first;
        while (++__i != __last)
            if (__comp(*__first, *__i))
                __first = __i;
    }
    return __first;
}

3번째 줄을 보면 중괄호로 묶었을 때, 알아서 list 객체를 생성해서 인자로 주는 방식임을 알 수 있다.

그렇다면 그냥 중괄호로 묶는 것과 max함수 안에 max를 넣는 방법 중 어느 것이 더 빠를까?

첫번째로 객체를 만드는 max값을 구하는 방법으로 측정한 시간을 보자.

#include<iostream>
#include<ctime>
using namespace std;

int main(){
    int arr[4] = {0, 1, 2, 3};
    int t = 100000000;
    double elapsedTime = clock();
    while (t--) {
        int wantValue = -1;
        wantValue = max({arr[0], arr[1], arr[2], arr[3]});
    }
    
    printf("총 걸린 시간은 %lf초 입니다.\n", (clock() - elapsedTime)/CLOCKS_PER_SEC);
    
    return 0;
}

두번째로는 그냥 max안에 max를 넣어 구하는 방법으로 측정한 시간을 보자.

#include<iostream>
#include<ctime>
using namespace std;

int main(){
    int arr[4] = {0, 1, 2, 3};
    int t = 100000000;
    double elapsedTime = clock();
    while (t--) {
        int wantValue = -1;
        wantValue = max(arr[0], max(arr[1], max(arr[2], arr[3])));
    }
    
    printf("총 걸린 시간은 %lf초 입니다.\n", (clock() - elapsedTime)/CLOCKS_PER_SEC);
    
    return 0;
}

이 결과를 보면 알 듯이 실제로 max 함수 안에 max를 넣으면 조금 더 빠른 것을 알 수 있다. 차이라고 하면 객체를 생성하는데에 걸리는 시간일 테니, 코딩 코스트는 줄어들지만 실제로 퍼포먼스적인 측면에서는 더 좋지 않음을 알 수 있다. 하지만 문제를 푸는 것에 있어서는 유의미한 결과를 가져오지는 않을 것으로 보이므로 코딩코스트가 줄어든다는 측면에서는 좋은 방법인듯 하다.