백준) 2342 Dance Dance Revolution

2342. Dance Dance Revolution

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

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 

1 2 2 4 0

예제 출력 

8

1. 접근

발의 위치가 5가지 혹은 4가지로 좁힐 수 있으니 뭔가 그리디 하게 풀 수 있을까 생각이 든다.

하지만 빡대가리로는 직관적인 그리디 방법이 떠오르지 않으므로 만만한 다이나믹 프로그래밍으로 완전탐색 해보자.

2. 풀이

항상 다이나믹 프로그래밍으로 풀 땐 dp배열을 잘 정의해야한다.

어떻게 정의하느냐에 따라 시간복잡도가 달라지고 시간제한에 걸릴지 말지 판가름 할 수 있기 때문이다.

두 발로 와리가리 하는걸 보니 왠지 경찰차 문제 http://js1jj2sk3.tistory.com/52 가 떠오르긴한다.

당시 dp배열은 dp[경찰차 1이 마지막으로 처리한 사건 번호][경찰차 2가 마지막으로 처리한 사건 번호]로 정의했었다.

사건은 천개가 맥시멈이니까 백만 안으로 들어오는 dp배열이 가능했었다.

이 방법으로 이 문제도 조질 수 있을까?

ddr 노트가 십만가 들어온다니까 불행히도 불가능하다.

그래서 내 생각으로는 일단 몇번째 노트 짼지는 기억해야 하니까 십만칸은 기본적으로 필요하다.

또한 직관적으로 왼발 오른발의 상태를 나타내야하니 5 * 5 = 25 칸도 필요하다.

그래서 걍 25 * 십만칸으로 조지기로 하자. 이래버리면 20 MB 정도 써야한다 ㅜㅜ

(분명히 더 나은 방법이 있다. 맞은사람들을 보면 1MB 쓴 사람도 있다.)

그래서 dp[왼발 위치][오른발 위치][다음에 밟을 노트가 몇번째] 로 정의하고 나면

함수는 func(int l, int r, int i) = 현재 상태가 이러저러 할 때 앞으로 힘을 얼마나 더 써야하는지 최소량으로 정의된다.

함수의 기저사례는 i가 끝까지 가버려서 게임을 다해버린 경우다.

아니라면 두 발의 상태에 따라 함수가 다르게 확장된다.

먼저 두 발이 중앙에 있었다면, 다음 노트에 따라 왼발을 옮기든지 오른발을 옮기든지 하면 된다.

따라서 두 경우를 구해보고 최소값을 리턴하자. 

하지만 잘 생각해보면, 무조건 왼발/오른발을 옮겨도 똑같은 결과다.

다음 경우는 다음 노트가 내 두발 중 하나랑 겹치는 경우다.

이 때는 발은 그대로고 힘을 1만큼 쓰기만 하면 된다.

마지막 경우는 완전 새로운 노트로, 왼발을 옮길지, 오른발을 옮길지 따져봐야 한다.

또한 발을 옮길 때 힘을 다르게 쓰므로 주의하자.

중앙에서 옮기면 2을, 반대편으로 가면 4를, 아니면 3만큼의 힘을 쓴댄다.

3. 코드

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
int step[100001];
int dp[5][5][100001];
int len;
 
int func(int l, int r, int i) {
    if (i == len)
        return 0;
 
    int& ref = dp[l][r][i];
    if (ref != -1)
        return ref;
 
    if (l == 0 && r == 0)
        return ref = func(step[i], r, i + 1) + 2;
 
    if (l == step[i])
        return ref = func(l, r, i + 1) + 1;
    else if (r == step[i])
        return ref = func(l, r, i + 1) + 1;
 
    int left = 0;
    if (l == 0)
        left = func(step[i], r, i + 1) + 2;
    else if (abs(l - step[i]) == 2)
        left = func(step[i], r, i + 1) + 4;
    else
        left = func(step[i], r, i + 1) + 3;
 
    int right = 0;
    if (r == 0)
        right = func(l, step[i], i + 1) + 2;
    else if (abs(r - step[i]) == 2)
        right = func(l, step[i], i + 1) + 4;
    else
        right = func(l, step[i], i + 1) + 3;
 
    return ref = min(left, right);
}
 
int main() {
    int tmp;
    while (1) {
        scanf("%d", &tmp);
        if (tmp == 0)
            break;
        else
            step[len++] = tmp;
    }
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, 0, 0));
 
    return 0;
}

4. 후기

재귀질이니까 바텀업보다 메모리도 시간도 더 쓰긴한다. 코드를 좀 더 간결하게 써서 시간을 최대한 줄여보자.