백준 2342번

오늘 풀어본 문제는 백준의 2342번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

승환이는 요즘 “Dance Dance Revolution”이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.

DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 $0$ , 위를 $1$ , 왼쪽을 $2$ , 아래를 $3$ , 오른쪽을 $4$ 라고 정하자.

DDR

처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.

이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 $1$ 의 위치에 있고, 다른 한 발이 $3$ 의 위치에 있을 때, $3$ 을 연속으로 눌러야 한다면, $3$ 의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.

오랫동안 DDR을 해 온 백승환은 발이 움직이는 위치에 따라서 드는 힘이 다르다는 것을 알게 되었다. 만약, 중앙에 있던 발이 다른 지점으로 움직일 때, $2$ 의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 $3$ 의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 $4$ 의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 $1$ 의 힘을 사용하게 된다.

만약 $1 \to 2 \to 2 \to 4$ 를 눌러야 한다고 가정해 보자. 당신의 두 발은 처음에 (point $0$ , point $0$ )에 위치하여 있을 것이다. 그리고 $(0, 0) \to (0, 1) \to (2, 1) \to (2, 1) \to (2, 4)$ 로 이동하면, 당신은 $8$ 의 힘을 사용하게 된다. 다른 방법으로 발을 움직이려고 해도, 당신은 $8$ 의 힘보다 더 적게 힘을 사용해서 $1 \to 2 \to 2 \to 4$ 를 누를 수는 없을 것이다.

입력

입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 $1$ , $2$ , $3$ , $4$ 의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 $0$ 은 수열의 마지막을 의미한다. 즉, 입력 파일의 마지막에는 $0$ 이 입력된다. 입력되는 수열의 길이는 $100,000$ 을 넘지 않는다.

출력

한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 힘을 출력한다.

풀이과정

1번째 시도

문제를 보고 DP 문제라는 것을 알 수 있었다. 3차원 배열을 이용하여 이를 해결하기로 했고, 첫 번째 인덱스는 현재 스텝, 두 번째 인덱스는 왼쪽 발의 위치, 세 번째 발의 인덱스는 오른쪽 발의 위치로 설정하였다.

각 인덱스에 저장된 값은 해당 상태에 도달하기까지 필요한 힘의 최소값이며, 만약 해당 상태에 도달하는 것이 불가능하다면 INT_MAX 를 저장하도록 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int getPower(int start, int end);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<int> ddr;

    while (true) {
        int temp;
        cin >> temp;

        if (temp == 0) {
            break;
        }
        else {
            ddr.emplace_back(temp);
        }
    }

    if (ddr.empty()) {
        cout << 0;
        return 0;
    }

    vector<vector<vector<int>>> dp(ddr.size(), vector<vector<int>>(5, vector<int>(5, INT_MAX)));

    dp[0][ddr[0]][0] = getPower(0, ddr[0]);
    dp[0][0][ddr[0]] = getPower(0, ddr[0]);

    for (int step=1; step<ddr.size(); step++) {
        for (int right=0; right<5; right++) {
            if (ddr[step] == right) {
                continue;
            }

            for (int prevLeft=0; prevLeft<5; prevLeft++) {
                int prev = dp[step-1][prevLeft][right];
                int curr = prev + getPower(prevLeft, ddr[step]);

                if (prev != INT_MAX && dp[step][ddr[step]][right] > curr) {
                    dp[step][ddr[step]][right] = curr;
                }
            }
        }

        for (int left=0; left<5; left++) {
            if (ddr[step] == left) {
                continue;
            }

            for (int prevRight=0; prevRight<5; prevRight++) {
                int prev = dp[step-1][left][prevRight];
                int curr = prev + getPower(prevRight, ddr[step]);

                if (prev != INT_MAX && dp[step][left][ddr[step]] > curr) {
                    dp[step][left][ddr[step]] = curr;
                }
            }
        }
    }

    int result = INT_MAX;

    for (int left=0; left<5; left++) {
        for (int right=0; right < 5; right++) {
            result = min(result, dp[ddr.size() - 1][left][right]);
        }
    }

    cout << result;

    return 0;
}

int getPower(int start, int end) {
    if (start == end) {
        return 1;
    }
    else if (start == 0) {
        return 2;
    }
    else if (abs(start - end) == 2) {
        return 4;
    }
    else {
        return 3;
    }
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

또 DP 문제가 나오고 말았다! DP 문제는 언제나 아이디어 싸움인 것 같다. 그리고 그런 아이디어가 번쩍번쩍 잘 떠오르면 좋을텐데, 아직 그정도의 실력이 되는 것 같지는 않다. 그리고 아이디어가 떠올랐다고 해도, 그걸 구현하는건 다른 이야기인 것 같다.

이제 군대가기까지는 $9$ 일이, CLASS 5 는 $6$ 문제가 남은 상황이다. 이 페이스를 잘 유지한다면 군입대 전에 CLASS 5 는 모두 해치우고 갈 수 있을 것 같다. 마저 힘내서 풀어봐야 겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/2342

← Previous Post Next Post →