[백준] 2579번

상당히 역겨운 문제다.

왜냐하면, 나는 문해력이 딸리기 때문이다.

이 문제에서 가장 큰 문제는 세 칸을 연속으로 밟을 수 없다는 것인데, start는 계단으로 취급하지 않는다.

이 말은 즉, 시작은 0

이후에 계단을 오르면 모든 상태에서 1이다는 뜻이다. 연속이 아닐 뿐, 한칸 올라갔기 때문이다.

이걸 눈치채지 못해서 너무 헤맸다.

 

그리고, 너무 뇌빼고 했나 out of bound 부분이 당연히 stair에서 일어날 수 밖에 없는데, 왜 까먹고 있었는지가 우습다.

 

다시한번 깨닫는다. 문제를 해결하기 위해서는 말을 이해해야 하고, 관리를 철저히 해야한다는 것을 알았다.

#include <iostream>
#include <map>


int main() {
    int height, index = 0, cnt = 1, m = 0;
    std::cin >> height;
    int stair[height+1];
    for (int i = 1; i <= height; i++) {
        std::cin >> stair[i];
    }
    stair[0] = 0;

    std::map<int, std::pair<int, int>> queue; // floor / status 순 0 -> start or 2칸 / 1-> 이전에 1칸 / 2-> 이전, 이전에 1칸 -> 2칸만
    std::map<std::pair<int, int>, int> visited;

    std::pair<int, int> state = {0, 0};
    queue[0] = state;
    visited[state] = 0;

    while (cnt > index) {
        std::pair<int, int> new_state[2] = {{queue[index].first+1, queue[index].second+1}, {queue[index].first+2, 1}};
        for (int i = 0; i < 2; i++) {
            if (new_state[i].second > 2 || new_state[i].first > height) {
                continue;
            }
            if (visited[queue[index]] + stair[new_state[i].first] > visited[new_state[i]] || visited[new_state[i]] == 0) {
                visited[new_state[i]] = visited[queue[index]]+ stair[new_state[i].first];
                queue[cnt++] = new_state[i];
            } else if (visited[queue[index]] + stair[new_state[i].first] > visited[new_state[i]]) {
                visited[new_state[i]] = visited[queue[index]]+ stair[new_state[i].first];
            }
        }
        index++;
    }

    for (int i = 0; i< 3; i++) {
         if (m < visited[{height, i}]) {
             m = visited[{height, i}];
         }
    }

    std::cout << m << std::endl;


    return 0;
}