2096 내려가기

2096 내려가기 (c++)

문제

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

접근 방식

DP

1. 다음 칸은 현재 칸과 인접한 칸 (좌우로 1칸씩)만 선택 가능
2. 매번 현재 열 + 이전 행의 인접한 열 중 큰 값을 선택 (DP)

문제 풀이

#include <iostream>
using namespace std;
inline int Max(int a, int b) { return a > b ? a : b; }
inline int Min(int a, int b) { return a < b ? a : b; }
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    char input[3];
    int N, maxArr[3], minArr[3], temp[3];
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> input[0] >> input[1] >> input[2];

        if (i == 0)
        {
            maxArr[0] = minArr[0] = input[0] - '0';
            maxArr[1] = minArr[1] = input[1] - '0';
            maxArr[2] = minArr[2] = input[2] - '0';
        }
        else
        {
            temp[0] = input[0] - '0' + Max(maxArr[0], maxArr[1]);
            temp[1] = input[1] - '0' + Max(Max(maxArr[0], maxArr[1]), maxArr[2]);
            temp[2] = input[2] - '0' + Max(maxArr[1], maxArr[2]);
            maxArr[0] = temp[0];
            maxArr[1] = temp[1];
            maxArr[2] = temp[2];

            temp[0] = input[0] - '0' + Min(minArr[0], minArr[1]);
            temp[1] = input[1] - '0' + Min(Min(minArr[0], minArr[1]), minArr[2]);
            temp[2] = input[2] - '0' + Min(minArr[1], minArr[2]);
            minArr[0] = temp[0];
            minArr[1] = temp[1];
            minArr[2] = temp[2];
        }
    }

    cout << Max(Max(maxArr[0], maxArr[1]), maxArr[2]) << " " << Min(Min(minArr[0], minArr[1]), minArr[2]) << '\n';


    return 0;
}

다시 생각해 볼 점

1. 헤더의 max, min을 사용하는 것보다, 직접 inline 으로 구현하는게 실행 속도가 빠르다.
2. input이 0 ~ 9이기때문에 int로 받는것 보다 char 로 받아서 - ‘0’하여 사용하는게 속도면에서 우수했다.
3. 현재값, 이전값, 입력값만 필요하기 때문에 입력받은 배열 모두를 저장할 필요가 없다. (모두를 저장하려고 했을 땐 메모리 초과가 떴음)