BOJ2342 Dance Dance Revolution

2342번 DDR

 

 

뭔가 경찰차랑 비슷한 느낌의 DP

눌러야하는 DDR의 발판 번호가 주어지면 발판을 순서대로 누르기 위한 최소의 힘을 구해야 한다.

 

a[ i ][ j ]=이번 발판까지 고려하여 오른발이 i, 왼발이 j를 누를 때 사용한 최소의 힘

 

 

STEP 1. 발의 움직임에 따라 사용하는 힘을 배열에 저장

사차원 배열을 이용했다.

p[ a ][ b ][ c ][ d ]=오른발 a, 왼발 b에서 오른발 c, 왼발 d 가 될 때 사용하는 힘

//same posit: 1		i,j -> i,j i=0-4 j=0-4
//0->1/2/3/4: 2		i,0 -> i,j i=0-4 j=1-4
//moving adj: 3		i,j -> i,j+1
//moving opp: 4

	//STEP 1. Set Power p
	int p[5][5][5][5] = { 0, };
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) p[i][j][i][j] = 1;
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = 1; j < 5; ++j) p[i][0][i][j] = p[0][i][j][i] = 2;
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = 1; j < 4; ++j) p[i][j][i][j + 1] = p[j][i][j + 1][i] = 3;
		for (int j = 2; j < 5; ++j) p[i][j][i][j - 1] = p[j][i][j - 1][i] = 3;
		p[i][4][i][1] = p[4][i][1][i] = p[i][1][i][4] = p[1][i][4][i] = 3;
	}
	for (int i = 0; i < 5; ++i) {
		p[i][1][i][3] = p[i][3][i][1] = p[1][i][3][i] = p[3][i][1][i] = 4;
		p[i][2][i][4] = p[i][4][i][2] = p[2][i][4][i] = p[4][i][2][i] = 4;
	}

p에서 사용되지 않는 공간이 존재하지만,, 이게 편해서 이렇게 했다.

 

 

STEP 2. 첫 번째 입력 처리

[ 0 ][ 0 ]인 상태에서 [ 0 ][ pre ] 또는 [ pre ][ 0 ]인 상태가 될 수 있다.

 

 

STEP 3. 두 번째부터 마지막까지 입력 처리

STEP 3-1. 입력 or 출력

pre: 직전에 누른 발판의 번호. 첫 번째 입력에서는 어차피 다음 단계에 사용될 거기 때문에 pre로 받음(40행)

num: 현재 눌러야 할 발판의 번호

dp: 직전 시행까지의 값을 저장해둔 구조체

newdp: 이번 시행의 값을 저장할 구조체

 

따라서 출력하게 될 경우 dp.a[ pre ][ * ]와 dp.a[ * ][ pre ] 중 최솟값을 출력한다.

pre 변수를 쓰지 않는다면 그냥 dp.a를 전부 탐색해 0인 값을 제외하고 최솟값을 출력하면 된다.

여기서 또한 사용되지 않는 공간이 a에 존재하겠지만,, 예 이게 편하구요

 

STEP 3-2. num을 눌러 소모한 총 힘의 양 계산

직전 상태에서 현재 상태로 바뀔 수 있는 모든 경우에 대해 계산한다.

직전 상태는 왼발이 pre를 눌렀거나(3-13행) 오른발이 pre를 눌렀던(14-24행) 상태.

직전 발판-현재 발판을 누르는 발이 왼-왼, 왼-오, 오-오, 오-왼인 경우 각각 구한다.

	//STEP 3-2. Compute New Power
	ddr newdp;
	//(i,pre)->(i,num) or (i,pre)->(num,pre)
	for (int i = 0; i < 5; ++i) {
		int curpow = dp.a[i][pre];
		if (!curpow) continue;

		if (!newdp.a[i][num]) newdp.a[i][num] = curpow + p[i][pre][i][num];
		else newdp.a[i][num] = min(newdp.a[i][num], curpow + p[i][pre][i][num]);

		if (!newdp.a[num][pre]) newdp.a[num][pre] = curpow + p[i][pre][num][pre];
		else newdp.a[num][pre] = min(newdp.a[num][pre], curpow + p[i][pre][num][pre]);
	}
	//(pre,j)->(num,j) or (pre,j)->(pre,num)
	for (int j = 0; j < 5; ++j) {
		int curpow = dp.a[pre][j];
		if (!curpow) continue;
		
		if (!newdp.a[num][j]) newdp.a[num][j] = curpow + p[pre][j][num][j];
		else newdp.a[num][j] = min(newdp.a[num][j], curpow + p[pre][j][num][j]);

		if (!newdp.a[pre][num]) newdp.a[pre][num] = curpow + p[pre][j][pre][num];
		else newdp.a[pre][num] = min(newdp.a[pre][num], curpow + p[pre][j][pre][num]);
	}
	dp = newdp;	pre = num;

pre변수를 사용하지 않으면 아래처럼 할 수 있다. 연산 횟수의 차이가 있겠지만 애초에 a가 작아 시간 차이가 크진 않은 듯.

	//STEP 3-2. Compute New Power
	ddr newdp;
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) {
			int curpow = dp.a[i][j];
			if (!curpow) continue;
			//(i,j)->(num,j) or (i,j)->(i,num)
			
			if (!newdp.a[num][j]) newdp.a[num][j] = curpow + p[i][j][num][j];
			else newdp.a[num][j] = min(newdp.a[num][j], curpow + p[i][j][num][j]);

			if (!newdp.a[i][num]) newdp.a[i][num] = curpow + p[i][j][i][num];
			else newdp.a[i][num] = min(newdp.a[i][num], curpow + p[i][j][i][num]);
		}
	}
	dp = newdp;	

 

 

전체 코드

 

#include <cstdio>
#include <algorithm>
using namespace std;

//  1
//2 0 4
//  3 

//same posit: 1		i,j -> i,j i=0-4 j=0-4
//0->1/2/3/4: 2		i,0 -> i,j i=0-4 j=1-4
//moving adj: 3		i,j -> i,j+1
//moving opp: 4

struct ddr {
	int a[5][5] = { 0, };
};
//a[i][j]=power with right on i, left on j

int main() {
	//STEP 1. Set Power p
	int p[5][5][5][5] = { 0, };
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) p[i][j][i][j] = 1;
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = 1; j < 5; ++j) p[i][0][i][j] = p[0][i][j][i] = 2;
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = 1; j < 4; ++j) p[i][j][i][j + 1] = p[j][i][j + 1][i] = 3;
		for (int j = 2; j < 5; ++j) p[i][j][i][j - 1] = p[j][i][j - 1][i] = 3;
		p[i][4][i][1] = p[4][i][1][i] = p[i][1][i][4] = p[1][i][4][i] = 3;
	}
	for (int i = 0; i < 5; ++i) {
		p[i][1][i][3] = p[i][3][i][1] = p[1][i][3][i] = p[3][i][1][i] = 4;
		p[i][2][i][4] = p[i][4][i][2] = p[2][i][4][i] = p[4][i][2][i] = 4;
	}
	
	//STEP 2. First Input
	int num, pre;
	scanf("%d", &pre);
	if (!pre) { printf("0"); return 0; }

	ddr dp;
	dp.a[pre][0] = dp.a[0][pre] = 2;
	
	//STEP 3. Second~Final Input
	while (1) {
		//STEP 3-1. Get Input or Return
		scanf("%d", &num);
		if (!num) {
			int MIN = 987654321;
			for (int j = 0; j < 5; ++j) {
				if (dp.a[pre][j])MIN = min(MIN, dp.a[pre][j]);
				if (dp.a[j][pre])MIN = min(MIN, dp.a[j][pre]);
			}
			printf("%d", MIN);
			return 0;
		}

		//STEP 3-2. Compute New Power
		ddr newdp;
		//(i,pre)->(i,num) or (i,pre)->(num,pre)
		for (int i = 0; i < 5; ++i) {
			int curpow = dp.a[i][pre];
			if (!curpow) continue;

			if (!newdp.a[i][num]) newdp.a[i][num] = curpow + p[i][pre][i][num];
			else newdp.a[i][num] = min(newdp.a[i][num], curpow + p[i][pre][i][num]);

			if (!newdp.a[num][pre]) newdp.a[num][pre] = curpow + p[i][pre][num][pre];
			else newdp.a[num][pre] = min(newdp.a[num][pre], curpow + p[i][pre][num][pre]);
		}
		//(pre,j)->(num,j) or (pre,j)->(pre,num)
		for (int j = 0; j < 5; ++j) {
			int curpow = dp.a[pre][j];
			if (!curpow) continue;
		
			if (!newdp.a[num][j]) newdp.a[num][j] = curpow + p[pre][j][num][j];
			else newdp.a[num][j] = min(newdp.a[num][j], curpow + p[pre][j][num][j]);

			if (!newdp.a[pre][num]) newdp.a[pre][num] = curpow + p[pre][j][pre][num];
			else newdp.a[pre][num] = min(newdp.a[pre][num], curpow + p[pre][j][pre][num]);
		}
		dp = newdp;	pre = num;
	}
}

 

 

 

 

뭔가 p배열 만드는 것 때문에 약간 구현 느낌 났다. 나만그런지

볼수록 경찰차와 비슷한 문제같다.

낭비되는 공간이 좀 있는데 더 명료하면서 나은 방법이 딱히 떠오르지 않는다.

SDS강의로 일차원적인 수열 외 더 다양한 DP를 풀어볼 수 있었던 듯