BOJ-2342-Dance Dance Revolution

[changicho]

2342. Dance Dance Revolution

링크

난이도	정답률(_%)
Gold I	34.129

설계

동적계획법

정리

내 코드 (ms)	빠른 코드 (ms)
28

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>

#define SIZE 100000+1
#define STEP 4+1
#define INF 1000000

using namespace std;

int arr[SIZE];
int dp[SIZE][STEP][STEP];

int calc(int a, int b) {
	if (a == b) return 1;
	if (a == 0 || b == 0) return 2;

	if (a < b) swap(a, b);
	if (a == 4 && b == 1) {
		return 3;
	}

	return a - b + 2;
}

void solution() {
	int num, N = 0;

	for (int i = 1;; i++) {
		cin >> num;
		if (num == 0) break;

		arr[i] = num;
		N++;		// count of nums in arr (it also means last index of arr)
	}

	memset(dp, INF, sizeof(dp));

	dp[1][arr[1]][0] = 2;
	dp[1][0][arr[1]] = 2;
	dp[0][0][0] = 0;

	for (int i = 2; i <= N; i++) {
		for (int left = 0; left <= 4; left++) {
			for (int right = 0; right <= 4; right++) {
				if (left == right) continue;
				if (left != arr[i] && right != arr[i]) continue;

				for (int next = 0; next <= 4; next++) {
					if (left == arr[i]) dp[i][left][right] = min(dp[i][left][right], dp[i - 1][next][right] + calc(next, left));
					if (right == arr[i]) dp[i][left][right] = min(dp[i][left][right], dp[i - 1][left][next] + calc(next, right));
				}
			}
		}
	}

	int answer = 1000000;
	for (int step = 0; step <= 4; step++) {
		if (step == arr[N]) continue;
		answer = min(answer, dp[N][arr[N]][step]);
		answer = min(answer, dp[N][step][arr[N]]);
	}

	if (answer >= 1000000) {
		answer = 0;
	}

	cout << answer << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}