[BOJ] 2432 Dance Dance Revolution

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

2342번: Dance Dance Revolution

 

재귀함수와 DP를 이용하는 문제

왼발이랑 오른발이 따로 움직여서 처음엔 뭔가 싶었다.

i번째에 왼발 오른발이 어디에 있는지 저장해서 풀 수 있었다.

그때 들이는 가장 적은 힘을 배열에 저장해뒀다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int i;
int order[100001];
int power[100001][5][5];

int move(int from, int to) {
	if (from == to) return 1;
	else if (from == 0) return 2;

	switch (from) {
	case 1: return to == 3 ? 4 : 3;
	case 2: return to == 4 ? 4 : 3;
	case 3: return to == 1 ? 4 : 3;
	case 4: return to == 2 ? 4 : 3;
	}
}

int DDR(int n, int left, int right) {
	if (n == i - 1) return 0;

	if (power[n][left][right] != 0) return power[n][left][right];

	return power[n][left][right] = std::min(move(left, order[n]) + DDR(n + 1, order[n], right),
		move(right, order[n]) + DDR(n + 1, left, order[n]) );
}

int main() {
	while (1) {
		scanf("%d", &order[i++]);
		if (order[i - 1] == 0) break;
	}

	printf("%d", DDR(0, 0, 0));

	return 0;
}

 

후기)

진짜 오랜만에 백준을 풀었다.

한학기동안 알고리즘 수업을 들어서 예전보다 쉽게 풀 줄 알았는데 어림도 없었다.

C++도 오랜만이라 일단 C로 풀었다...

배열 크기 잡는 것도 실수해서 왜 안되냐하고 30분은 헤맸다.

역시 컴퓨터는 거짓말을 안 한다. 다 내 잘못임.

알고리즘 수업 들을 땐 이런 문제들에 대해 priciple of optimality를 적용할 수 있는지

증명을 한번씩 했었는데 세상 너무 귀찮다.

풀만한 문제를 찾다보니 위상정렬 문제가 많이 보였다.

다음엔 그걸 한번 풀어봐야겠다.