[백준]Dance Dance Revolution(2342)

문제 링크 : [백준]Dance Dance Revolution(2342)

문제 설명

두 발이 처음에는 위치 0에서 시작합니다.
왼쪽 발과 오른쪽 발을 주어진 위치(1,2,3,4)로 옮겨야 하며, 두 발중 아무 발이나 옮길 수 있습니다. 단, 옮긴 후, 두 발이 같은 위치에 있으면 안됩니다.
발을 옮길 때마다 아래와 같이 비용이 발생합니다.

1. 0 -> 다른 곳 : 2
2. 1 <-> 3, 2 <-> 4 : 4
3. 같은 곳을 다시 밟는 경우 : 1
4. 그 외 : 3

밟을 곳이 주어진다면 모두 밟는 경우 중 최소 비용을 구하세요.

입력

B_i(밟을 판의 위치, 0인 경우 종료, 최대 100,000개를 초과하여 주어지지 않습니다.)

1 2 2 4 0

출력

8

카테고리

#DP

시간 복잡도 상한

O(NlongN)

해결 방법

1. 발판이 주어지면, 두 발을 각각 이동시켜가며 Brute force 방식으로 구할 수 있습니다.
2. 단, 시간 복잡도를 따지면, O(2ⁿ) 이 걸립니다.
3. n이 10만이면 재귀로 구현하는 것자체가 어려울 것 같습니다.(맞은 사람을 보니 가능한 것 같기는 합니다. 대략 재귀 1만 Depth면 스택 1MB에서 터지는 것 같습니다.)
4. 현재 발의 위치까지 만드는데 최소 비용이 주어진다면, 다음 발의 위치까지 가는 경우의 최소 비용을 구할 수 있습니다.
5. D[l][r][N]=N번째까지 오는데 왼쪽발의 위치는 l, 오른쪽 발의 위치는 r로 하는 최소비용
6. D[l][r][N]=min(D[05][r][N-1]+왼쪽 발을 현재 위치로 옮기는 비용, 단 05 중 r과 같은 경우는 제외)
7. D[l][r][N]=min(D[l][05][N-1]+오른쪽 발을 현재 위치로 옮기는 비용, 단 05 중 r과 같은 경우는 제외)
8. 6과 7을 종합하여 최소값을 구합니다.

시간복잡도

O(55N) => O(N)

코드

#include<iostream>
#include<string.h>
#include<algorithm>
#define F for(i=0;i<5;i++)for(j=0;j<5;j++)
#define M 999999
using namespace std;
int d[5][5][2],x,a,i,j,t,s[5][5]={{0,2,2,2,2},{0,1,3,4,3},{0,3,1,3,4},{0,4,3,1,3},{0,3,4,3,1}};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    F d[i][j][0]=d[i][j][1]=M;
    cin>>x;
    if(!x){
        cout<<0;
        return 0;
    }
    d[x][0][0]=d[0][x][0]=2;
    while(1){
        cin>>x;
        if(!x)break;
        F d[i][j][!t]=M;
        F{
            if(x!=i)d[i][x][!t]=min(d[i][x][!t],d[i][j][t]+s[j][x]);
            if(x!=j)d[x][j][!t]=min(d[x][j][!t],d[i][j][t]+s[i][x]);
        }
        t=!t;
    }
    a=M;
    F a=min(a,d[i][j][t]);
    printf("%d",a);
}