백준온라인 2342번 [Dance Dance Revolution] [C++]

www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

---

문제 요약

1. 발판이 5개 존재하고 특정 발판에서 다음 발판을 밟을 때 cost는 경우에 따라 다르긴 하지만 고정값임

2. 입력으로 밟아야 되는 발판이 주어지면 cost가 최소로 될 수 있는 값을 출력

3. 왼발과 오른발은 서로 다르게 움직일 수 있고 처음 시작점은 두발 모두 가운데에 위치

(입력 N의 개수 <=100,000)

---

나의 풀이

만약 입력이 1 -> 2 -> 2 -> 4라고 할 때

2번째 발판을 밟아야 할 때 오른발, 왼발 어느 발로 밟아야지 최종적으로 이득인지는

그다음(3 ,4 ,.... N번째 밟아야 하는 발판)을 알기 전까지는 알 수가 없다

 

 

그래서 입력을 제대로 확인하지 않고 시뮬레이션 느낌으로

struct info {

  left ;

  right;

  cost ; 

}

queue <info>

이런 식으로 큐를 이용해서 모든 경우를 탐색하면 되지 않을까 생각했었지만

이러면 큐에 최대로 들어가는 개수가 $2^N$ 개 가 돼서 터진다 

(왼발 , 오른발 중 무엇으로 해결할 건지 때문에 지수적으로 증가)

 

 

그러므로 시간의 흐름(입력 순)에 따라 cost의 최솟값을 갱신해야 풀이가 가능할 거 같아서

DP로 풀어야 되겠다는 생각이 들었다.

 

개인적으로 DP는 점화식, 배열의 구조가 2차원 배열을 예시로

d [i][] 하나의 차원은 (시간 , 순서)처럼 사건의 진행방향 증가하는 형태로 존재

d [][j]다른 하나의 차원은 해당 시간, 순서의 변수 상태 (어느 시간에 다양한 상태가 존재할 경우)

     j는 문제에 따라서 필요 없는 문제도 있다 ( 시간 외에 다른 변수가 없을 경우)

를 저장해야 하는 것으로 나름 정리하여 생각하고 있다

 

하지만 이문제는 오른발 왼발의 조합 이 상태의 변수가 되므로

나는 d [왼발 위치][ 오른발 위치][시간]을 배열로 놓고 시간의 증가에 따라서 최솟값을 갱신해주었다

---

느낀 점

DP문제라는 확신이 들 때는...   

(보통 이전 상태의 최솟값이 다음 상태의 최솟값을 보장한다는 느낌이 든다면...)

1.(bottom-up , top-down) 어느 것이 더 구현상 편한지

2. 배열의 차원을 어떻게 구상해야 좋을지

생각을 하면서 구현하는 게 중요하다는 생각이 든다

 

---

 

코드

 

	#include<iostream>
	#include<algorithm>
	#include<queue>
	#include<cmath>
	#define MAX 100'001
	#define INF 0x3f3f3f3f
	using namespace std;
	int d[5][5][MAX];
	int getCost(int cur ,int next){
	if(cur==0)return 2;
	if(cur==next)return 1;
	if(abs(cur-next)==2)return 4;
	return 3;
	}
	int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int i=0;i<MAX;i++){
	for(int j=0;j<5;j++){
	for(int k=0;k<5;k++){
	d[j][k][i]=INF;
	}
	}
	}
	d[0][0][0]=0;
	int n,idx=0;
	while(1){
	cin>>n;
	if(n==0)
	break;
	for(int i=0;i<5;i++){
	for(int j=0;j<5;j++){
	if(d[i][j][idx]==INF)
	continue;
	int lc = getCost(i,n);
	int rc = getCost(j,n);
	d[n][j][idx+1]=min(d[n][j][idx+1],d[i][j][idx]+lc);
	d[i][n][idx+1]=min(d[i][n][idx+1],d[i][j][idx]+rc);
	}
	}
	idx++;
	}
	int ans=INF;
	for(int i=0;i<5;i++){
	for(int j=0;j<5;j++){
	ans = min(ans,d[i][j][idx]);
	}
	}
	cout<<ans;
	}

view raw .cpp hosted with ❤ by GitHub