백준 2096 내려가기

조금 쉬워보이는 것을 잡았다. 이해하기도 나쁘지 않고, 왠지 그림도 있어서 있어보인다.

문제는 쉽다. N*3 게임 판에서 한칸씩 내려가는데, 바로 밑이나 바로 밑과 붙어있는 칸만 갈 수 있다. 각 칸은 점수가 있고, 그 점수의 합이 최대가 되는것, 최소가 되는 것을 찾으면 된다.

 

처음 접근은 dp[N][N] 으로 정의해서 dp[i][j] = i 번째 줄에서 j번째 줄까지 최대값을 저장하려고 했다. 근데 이렇게 접근을 하면, 맨 마지막 줄에서부터 역순으로 탐색을 해야하고, 역순으로 탐색을 하는 도중에 어디 칸을 밟았는지도 저장을 따로 했어야 했다. 심지어 최소값 저장 DP, 최대값 저장 DP를 따로 저장해야 했다.

머리를 뜯다가 질문글을 슬쩍 슬쩍 봤는데, 좀 신기했다.

 

내가 접근했듯이 밑에서부터 한칸한칸 하는것보다, 맨 위 줄에서 내려오면서 3개 칸을 전부 계산하면서 내려가는 접근이 대다수였다. 그리고 가장 큰 차이점은, dp 배열을 딱 두 줄만 쓰는 것. 한번 지나가면 뒤 값은 다시 볼 일이 없으므로 그냥 날려버려도 되니까 그냥 두줄로 처리한다.

구현은 진짜 게임 진행되는 그 자체로 한줄씩 내려가면서 dp 배열 채워준다. 그리고 마지막 세 칸에 도착한것들의 최대/최소를 구하면 답이다.

---

#include <iostream>
#include <vector>
#include <cstring>
    
int main()
{
    int N;
    std::cin >> N;
    // std::vector<std::vector<int> > map(N, std::vector<int>(3, 0));
    int map[100001][3];
    memset(map, 0, sizeof(map));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            int tmp;
            std::cin >> tmp;
            map[i][j] = tmp;
        }
    }
    long long mindp[2][3];
    long long maxdp[2][3];
    memset(mindp, 0, sizeof(mindp));
    memset(maxdp, 0, sizeof(maxdp));

    mindp[0][0] = maxdp[0][0] = map[0][0];
    mindp[0][1] = maxdp[0][1] = map[0][1];
    mindp[0][2] = maxdp[0][2] = map[0][2];
    // dp배열들 맵 첫번째 값으로 초기화.

    for (int i = 1; i < N; i++)
    {
        maxdp[1][0] = map[i][0] + std::max(maxdp[0][0], maxdp[0][1]);
        maxdp[1][1] = map[i][1] + std::max(std::max(maxdp[0][0], maxdp[0][1]), maxdp[0][2]);
        maxdp[1][2] = map[i][2] + std::max(maxdp[0][1], maxdp[0][2]);

        maxdp[0][0] = maxdp[1][0];
        maxdp[0][1] = maxdp[1][1];
        maxdp[0][2] = maxdp[1][2];

        mindp[1][0] = map[i][0] + std::min(mindp[0][0], mindp[0][1]);
        mindp[1][1] = map[i][1] + std::min(std::min(mindp[0][0], mindp[0][1]), mindp[0][2]);
        mindp[1][2] = map[i][2] + std::min(mindp[0][1], mindp[0][2]);

        mindp[0][0] = mindp[1][0];
        mindp[0][1] = mindp[1][1];
        mindp[0][2] = mindp[1][2];
    }

    long long maxVal = std::max(std::max(maxdp[0][1], maxdp[0][0]), maxdp[0][2]);
    long long minVal = std::min(std::min(mindp[0][1], mindp[0][0]), mindp[0][2]);

    std::cout << maxVal << " " << minVal;


}

 

처음 접근을 너무 어렵고 메모리 크게 했어서 살짝쿵 아쉬웠는데 코드 이해는 쉬워서 좋았다.

처음에 혼자서 꼬아서 생각한게 삽질이 컸다. 그냥 문제 조건 나온대로 구현만 하면 딱인데... 이런...

그래도 구현이 괜찮아서 좋았다.

 

오늘도 평온한 하루가 되길. 슨민.