백준 #2096 내려가기

어제 이산구조 퀴즈를 준비하며 초등학교를 같이 나온 대학 동기 이ㅇㅇ군과 줌으로 스터디를 하였다. 그는 알고리즘 공부를 하고 있었는데, 이문제를 풀고 있었다. 그 친구가 내가 이산구조 공부하는 동안 bfs, dfs로 애를 쓰다 실패하는 것을 보고 이 문제는 그거로 푸는게 아니겠구나 직감할 수 있었다. 예전에 이런 유형의 문제를 풀어 본 적이 있어서 풀이가 생각이 났다. 문제는 기억이 나지 않지만 뿌듯했다. 

 결론부터 말하자면 이 문제는 DP를 이용하여 푸는 문제이다. 추가로 이 문제는 시간도 물론 신경써야 하지만 메모리가 입력을 배열에 저장하기조차도 턱없이 부족하다. 4mb라니...  잘 하는 사람들은 부족한 메모리를 통해 이 문제는 입력을 하나하나 받을 때마다 연산을 해주어야한다 유추를 할 수도 있겠다. 

풀이를 떠올리자 크게 고민없이 짜도 괜찮을 것 같아 마구잡이로 쓰다보니 코드가 정말 엉망진창이다. 그래서 이번엔 최대한 말로 풀어서 써볼까 한다ㅎ

 

3개의 숫자가 차례로 주어지고, 각자 자신의 위치에서 바로아래, 한칸아래에서 왼쪽, 한칸아래에서 오른쪽 이렇게 이동 할 수 있고, 

가장 밑으로 내려갔을 때 가질 수 있는 최댓값, 최솟값을 찾아야 한다. 

 

간단하게 생각해보면

x	y	z
1	2	3

이 때 우리가 1번 위치에서 현재 가질 수 있는 가장 큰 값과 가장 작은 값을 구한다 생각해보자. 1번 위치에서는 x번에서 내려온 값과 y번에서 내려오는 값을 비교하면 된다. 즉, x였을 때 가진 가장 큰 값과 y였을 때 가장 큰 값을 비교해 더 큰 값을 1번 위치에 있는 수의 값을 더하면 1번 위치에서의 최대값을 구할 수 있다는 것이다. 항상 가장 클 때와 가장 작을 때를 구하여 dp배열에 저장한다는 점에서 greedy한 풀이라고도 할 수 있겠다. 

 한번 더 해보자면 우리가 2번 위치에 있다 생각하면, x,y,z 위치에서 각자 가질 수 있는 최댓값들 중 가장 큰 값을 고르고, 마찬가지로 가장 작은 값을 골라서 현재 위치에 지정된 값을 더해주면 된다.

 

더러운 코드는 다음과 같다.

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
//#include <numbers>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
int n;

vector<pair<int,int>> list;
int dp[4];
int dp2[4];
int arr[4];

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

    cin>>n;
    cin>>arr[0]>>arr[1]>>arr[2];
    dp[0] = arr[0]; dp[1] = arr[1]; dp[2] = arr[2];
    dp2[0] = arr[0]; dp2[1] = arr[1]; dp2[2] = arr[2];
    int max_val = -1;
    int min_val = 999999;
    
    for(int i=0; i<n-1; i++)
    {
        int t_dp0, t_dp1, t_dp2;
        int t_dp20, t_dp21, t_dp22;
        
        cin>>arr[0]>>arr[1]>>arr[2];
        
        t_dp0 = arr[0] + max(dp[0], dp[1]);
        int tmp1 = max(dp[0], dp[1]);
        tmp1 = max(tmp1, dp[2]);
        t_dp1 = arr[1] + tmp1;
        t_dp2 = arr[2] + max(dp[1], dp[2]);
        dp[0] = t_dp0; dp[1]= t_dp1; dp[2] = t_dp2;
        
        t_dp20 = arr[0] + min(dp2[0], dp2[1]);
        int tmp2 = min(dp2[0], dp2[1]);
        tmp2 = min(tmp2, dp2[2]);
        t_dp21 = arr[1] + tmp2;
        t_dp22 = arr[2] + min(dp2[1], dp2[2]);
        
        dp2[0] = t_dp20; dp2[1] = t_dp21; dp2[2] = t_dp22;
    }
   
    
    for(int i=0; i<3; i++)
    {
        if(dp[i] > max_val)
        {
            max_val = dp[i];
        }
        if(dp2[i] < min_val)
        {
            min_val = dp2[i];
        }
    }
   
    cout<< max_val << '\n' << min_val;

    return 0;
}

다음에는 최대한 깔끔하게 코드를 정리해서 쓰는 것을 목표로 삼고 공부해야겠다.

 

개강하고도 간간히 백준문제를 아직은 풀 여유가 있어서 다행이다..