글 읽기 - 풀이방법..

ls123kr 5년 전 0

제 풀이방법에 문제가 있을까요??

DP[p][q] = p~q까지 색을 통일시키는데 필요한 횟수의 최소값으로 정의했습니다.

그래서 p~q에서 왼쪽과 오른쪽에서 각각 다른색이 나올 때 까지 찾고,

왼쪽영역의 색을 변경하는 경우, 오른쪽영역의 색을 변경하는 경우, 만약 양쪽이 같은 색이었다면 가운데를 변경시키는 경우 중 최소값을 구하려했습니다..

고수님들 도와주세용

#include<stdio.h>
#include<string.h>
int n, k, dp[201][201], arr[201];
int inline min(int a, int b) { return a < b ? a : b; }
int solve(int p, int q) {
	if (p >= q) return 0;
	if (dp[p][q] != -1)
		return dp[p][q];
	int h, pp = p, qq = q;	
	while (arr[pp] == arr[pp + 1])
		pp++;
	pp++;
	while (arr[qq] == arr[qq - 1])
		qq--;
	qq--;
	if (pp > qq) 
		return dp[p][q] = 0;
	h = solve(pp, q) + 1;
	h = min(h, solve(p, qq) + 1);
	if (arr[p] == arr[q]) {
		h = min(h, solve(pp, qq) + 1);
	}
	return dp[p][q] = h;
}
int main() {
	memset(dp, -1, sizeof(dp));
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	printf("%d\n", solve(0, n - 1));
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

풀이방법..

ls123kr 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말