[C/C++] Codeforce 448C - Painting Fence (분할정복, Divide and Conquer)

C. Painting Fence

time limit per test1 second

memory limit per test512 megabytes

inputstandard input

outputstandard output

 

Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of ai meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.

Input

The first line contains integer n (1 ≤ n ≤ 5000) — the number of fence planks. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a single integer — the minimum number of strokes needed to paint the whole fence.

 

<교수님이 짜신 코드>

#include<stdio.h>

int a[5005];

int solve(int i, int j)
{
	int hans, vans, mini, s, t;
	vans = j - i + 1;
	mini = a[i];
	
	for (int k = i+1; k <= j; k++) // 제일 작은 값 찾기
		if (mini > a[k]) mini = a[k];
	
	for (int k = i; k <= j; k++) // 모든 값을 제일 작은 값으로 빼주기
		a[k] -= mini;
	
	hans = mini; // 빼준 부분 기록
	
	for (int k = i; k <= j;)
	{
		if (a[k] == 0) { k++; } // 높이가 0인 부분은 건너뛰기
		else
		{
			s = k;
			t = s;
			while (t <= j && a[t] != 0) t++;
			hans += solve(s, t - 1);
			k = t;
		}
	}
	
	if (vans < hans) return vans;
	else return hans;
		
}

int main(void) 
{
	int n;
	int ans;
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	ans = solve(1, n);

	printf("%d\n", ans);
}

 

<나의 코드>

#include<stdio.h>

int arr[5001];

int DC(int start, int finish)
{
	int start_temp;
	int horizontal = 0;
	int vertical = finish - start + 1;
	int min = arr[start];

	// 최소값 찾기
	for (int i = start; i <= finish; i++)
	{
		if (arr[i] < min) min = arr[i];
	}

	// 배열 전체 원소들 최소값으로 빼주기
	for (int i = start; i <= finish; i++)
	{
		arr[i] -= min;
	}

	horizontal += min; // 값 저장


	// 분할정복
	for (int i = start; i <= finish; i++)
	{	
		if (arr[i] == 0) i++;
		else
		{
			start_temp = i; // 시작 포인트
			while (arr[i] != 0) i++; // 처음으로 0이 나오는곳 까지 탐색
			horizontal += DC(start_temp, i - 1); // 재귀 호출
		}
		i -= 1; // 이 루프가 끝나면 i++ 이 실행되므로 미리 1을 빼준다
	}

	if (vertical > horizontal) return horizontal;
	else return vertical;

}

int main(void)
{
	int n;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &arr[i]);
	}
	
	printf("%d", DC(1, n));
}

STEP 1

STEP 2

STEP3

STEP 4

 

알고리즘 연습 수업 시간에 풀이한 문제 인데 김성열 교수님이 짝신 코드와 내가 짠 코드는 차이점은 없다. 내가 이해하기 쉽도록 처음부터 혼자 짜보고 변수명도 익숙하게 바꾸었다. 분할정복 알고리즘 코드는 처음 짜봐서 알고리즘 자체는 이해가 가지만 코드 구현을 하는데 약간의 어려움이 있었다.

원리는 간단하게 설명하자면 답은 두가지로 나뉘는데

- 하나는 "만약 모든 stroke를 수직으로 한다면 ",

- 다른 하나는 "전부 수직으로 stroke를 하는 경우를 제외하면 적어도 한번은 가로로 stroke를 해야한다" 이다.

그렇기 때문에 만약 입력이 n = 5,  arr = [ 5, 4, 3, 2, 5 ] 이라면 배열원소들중 최소값을 찾아서 최소값으로 모든 배열원소 값을 빼준다. 그렇다면 마치 하나였던 섬이 해수면 상승으로 여러개의 섬으로 나뉘는 것처럼 작은 문제들로 나뉠 수 있다. 이런식으로 문제들을 분할하고 작은 문제들을 해결하는 방법을 분할정복 알고리즘이라고 한다. 분할정복 알고리즘은 추후 추가적인 공부를 한 뒤 정리해서 포스팅 하도록 하겠습니다. 

 

 

https://codeforces.com/problemset/problem/448/C

Problem - 448C - Codeforces