[백준 2096] - 내려가기(C++)[골드5]

📕문제

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

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

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

📗입력

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

📗출력

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

 

👀문제 해석

• 문제조건을 보면 시간제한과 메모리조건이 빡센걸 알 수 있다. [진짜 빡세다]
• 초기에 문제를 읽지 않고 n*n으로 배열을 할당했는데 문제를 읽어보니 높이는 n이고 가로는 3칸으로 고정되어있었다.
• 메모리와 시간을 최대한 효울적으로 이용해서 푸는 것이 중요하다!

🔎문제 풀이

• 다른사람들과 풀이가 다르다고 말할 수 있다.
  
  • 다른사람들의 코드는 죄다 노가다로 비교하고, 만약 가로가 3이 아니라면 써먹을 수 없는 코드다.
  • 그렇게 짜는 코드는 굉장히 싫어하기 때문에 문제를 푸는데 골치가 좀 아팠다.
• 어쨋든 이 문제도 DP를 사용하는 문제라서 이전 값들을 저장할 공간이 필요한데
   메모리제한때문에 잘 생각해서 짜야한다.
• 기본적으로 반복문은 (n-1)*3번 돈다.
• 안쪽 반복문을 돌때마다 그 줄에서 최대값과 최소값을 구해준다.
• 그리고 안쪽 바깥문이 다 돌면 층을 바꿔줘서 직전층에서 저장된 값들을 이용해서 구해준다.
  • 왼쪽 위 값, 위 값, 오른쪽 위 값(갈 수 있는 전제하에)
    각각을 현재 방문한 지역의 값에 더해서 최대값과 최소값을 구한다.
  • 이 최대값과 최소값을 저장해둬야한다. [기존 배열을 바꾸지않고]
• 바뀐값들을 저장하고, 층의 값들을 유지해야 하기에 1차원 배열을 4개 썼다.
  • 층의 값들을 유지하는 배열이 Max,Min / 바뀐값들을 저장하는 배열이 Big,Small이다.
• 안쪽 바깥문이 다돌면 Max와 Min값을 Big과 Small로 업데이트 시켜준다.

 

💻코드

/*
내려가기 골드5
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int Max[3] = {0,};
    int Big[3] = {0,};
    int Min[3] = {0,};
    int Small[3] = {0,};
    int graph[n][3];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < 3; i++)
    {
        Max[i] = graph[0][i];
        Min[i] = graph[0][i];
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            int value = Max[j];
            int svalue = Min[j];
            Big[j] = Max[j] + graph[i][j];
            Small[j] = Min[j] + graph[i][j];
            if (i > 0)
            {
                if (j - 1 >= 0)
                {
                    Big[j] = max(Big[j], Max[j - 1] + graph[i][j]);
                    Small[j] = min(Small[j], Min[j - 1] + graph[i][j]);
                }
                if (j + 1 < 3)
                {
                    Big[j] = max(Big[j], Max[j + 1] + graph[i][j]);
                    Small[j] = min(Small[j], Min[j + 1] + graph[i][j]);
                }
            }            
        }
        for (int k = 0; k < 3; k++)
        {
            Max[k] = Big[k];
            Min[k] = Small[k];
        }
    }
    int big = 0, small = INT_MAX;
    for (int i = 0; i < 3; i++)
    {
        big = max(big, Max[i]);
        small = min(small, Min[i]);
    }
    cout << big << " " << small;
}

 

✔느낀점

• 내가 생각했던 문제보다 쉬워서 허망했다. [가로칸을 3개로 고정시켜두다니..]
• 노가다로 단순비교만 하면 되는문제다.
• 하지만 나는 그렇게 풀진 않았다는 점.
  • 다른사람 코드 진짜 못생김.