BOJ-2449-전구

[changicho]

2449. 전구

링크

난이도	정답률(_%)
Platinum IV	43.173

설계

재귀로 dp를 구함

정리

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

고생한 점

코드

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

#define INF 987654321

using namespace std;

int dp[202][202] = { 0, };	// 전구 숫자 최대 200개
int arr[202];

int dynamic(int f, int b) {
	if (f == b) return 0;
	if (dp[f][b] != -1) return dp[f][b];

	dp[f][b] = INF;
	for (int k = f; k < b; k++) {
		int adder = arr[f] == arr[k + 1] ? 0 : 1;

		dp[f][b] = min(dp[f][b], dynamic(f, k) + dynamic(k + 1, b) + adder);
	}
	return dp[f][b];
}

void solution() {
	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	memset(dp, -1, sizeof(dp));

	cout << dynamic(0, N - 1) << "\n";
}

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

	solution();

	return 0;
}