[백준] 2096번: 내려가기 - C++

문제 출처:https://www.acmicpc.net/problem/2096

---

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

본문에는 나와있지 않지만 출처에 들어가서 문제를 확인해보면 메모리 제한이 4MB 밖에 안된다는 것을 알 수 있습니다. 

따라서 들어오는 입력을 전부 다 저장한뒤 문제를 푸는 것이 아니라 입력이 한 줄씩 들어올때 바로바로 계산을 해서 갱신을 

해주어야 합니다.

즉시 계산을 하는 방법은 임의의 배열(DP)를 만들어 입력이 들어올때 문제의 조건에 맞추어 최대 점수와 최소 점수를 구해 

배열에 저장해주면 됩니다. 

이해를 돕기 위하여 출처의 예제에 나와있는 입력에 대해서 그림으로 설명하겠습니다.

입력: 3                                출력: 18    6

   1    2    3

   4    5    6

   4    9    0

예제 입력에서 최대 점수를 구하는 방법입니다.

처음엔 DP배열에 아무 데이터도 없기 때문에 입력값 그대로 넣어줍니다.

두 번째 부터 입력값과 DP배열을 비교하여 DP배열을 수정해줍니다. 

지금 그림의 경우는 최대 점수를 구하기 때문에 더해서 비교했을때 더 큰 값으로 DP배열을 갱신 해줍니다.

최종적으로 구해진 DP배열에서 가장 큰 값을 출력해주면 최대 점수를 구할 수 있습니다.

최소 점수는 반대로 DP배열을 갱신해줄때 더 작은 값으로 갱신하고 최종적으로 만들어진 DP배열에서 

가장 작은 값을 선택하면 됩니다.

전체 소스입니다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
 
using namespace std;
 
int main(void)
{
    int n, maxDP[3] = { 0,0,0 }, minDP[3] = { 0,0,0 }, input[3], temp_0, temp_2;
    scanf("%d", &n);
    scanf("%d %d %d", &maxDP[0], &maxDP[1], &maxDP[2]);
    minDP[0] = maxDP[0]; minDP[1] = maxDP[1]; minDP[2] = maxDP[2];
 
 
    for (int i = 1; i < n; i++) {
        scanf("%d %d %d", &input[0], &input[1], &input[2]);
        //최대값을 구해주는 DP배열 
        temp_0 = maxDP[0]; temp_2 = maxDP[2];
        maxDP[0] = max(maxDP[0], maxDP[1]) + input[0];
        maxDP[2] = max(maxDP[1], maxDP[2]) + input[2];
        maxDP[1] = max(max(temp_0, maxDP[1]), temp_2) + input[1];
        //최소값을 구해주는 DP배열
        temp_0 = minDP[0]; temp_2 = minDP[2];
        minDP[0] = min(minDP[0], minDP[1]) + input[0];
        minDP[2] = min(minDP[1], minDP[2]) + input[2];
        minDP[1] = min(min(temp_0, minDP[1]), temp_2) + input[1];
    }
 
    printf("%d ", max(max(maxDP[0], maxDP[1]), maxDP[2]));
    printf("%d", min(min(minDP[0], minDP[1]), minDP[2]));
    return 0;
}