백준 2879 코딩은 예쁘게 c++

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

2879번: 코딩은 예쁘게

start부터 drag까지 1씩 뺐을때, 더했을때 비교해서 매 순간 제일 효율적인 상황으로 간다.

#include <iostream> // 실패코드
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>

using namespace	std;
vector<int> src, dst;
int res = 0, num;

bool isOk() {
	for (int i = 0; i < num; i++)
		if (src[i] != dst[i])
			return false;
	return true;
}

void	greedy(int start, int drag) {
	int prevDiff = 2147483647;
	while (true) {
		int curDiff = 0, plusDiff = 0, minusDiff = 0;
		bool zeroFlag = false;
		for (int i = 0; i < drag; i++) {
			curDiff += abs(src[start + i] - dst[start + i]);
			plusDiff += abs(src[start + i] + 1 - dst[start + i]);
			if (src[start + i] == 0)
				zeroFlag = true;
			minusDiff += abs(src[start + i] - 1 - dst[start + i]);
		}
		if (prevDiff <= curDiff)
			return ;
		prevDiff = curDiff;
		if (isOk()) {
			cout << res;
			exit(0);
		}
		if (zeroFlag)
			minusDiff = 2147483647;
		int lessDiff = min(curDiff, min(plusDiff, minusDiff));
		if (lessDiff == curDiff)
			return ;
		else if (lessDiff == plusDiff) {
			res++;
			for (int i = 0; i < drag; i++)
				src[start + i]++;
		}
		else if (lessDiff == minusDiff) {
			res++;
			for (int i = 0; i < drag; i++)
				src[start + i]--;
		}
	}
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin >> num;
	for (int i = 0; i < num; i++) {
		int input;
		cin >> input;
		src.push_back(input);
	}
	for (int i = 0; i < num; i++) {
		int input;
		cin >> input;
		dst.push_back(input);
	}
	for (int drag = num; drag > 0; drag--)
		for (int start = 0; start + drag <= num; start++)
			greedy(start, drag);
}

그런데 테케2번인

4
1 2 3 4
3 1 1 0

여기서 문제가 생긴다. 

1 2 3 4 에서 1씩 다 뺀 0 1 2 3보다 2번째부터 1씩 다 뺀 1 1 2 3이 정답에 더 가깝다. 그렇다 거꾸로 생각해야한다.

단순히 저기서 drag가 1부터 시작하면 안된다. 그럼 죄다 드래그 1 짜리로 연산하기 때문이다.

 

1 3 3 2 에선 33

3 1 1 2 에선 11 이렇게 최댓값, 최솟값 꼭짓점들을 먼저 처리해주는 로직으로 조져봤다.

근데 역시 테케 2번에서 역시 탈락.. 이로직으론 최적해를 찾을 수 없다.

#include <iostream> // 실패코드
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>

using namespace	std;
vector<int> diff;
int res = 0, num;
// 0 1 2 3 2
void topCase() {
	while (true) {
		int start = 0, end = 0;
		while (end < num - 1 && diff[end] <= diff[end + 1])
			end++;
		if (end == num - 1)
			return ;
		res++;
		start = end;
		while (start > 0 && diff[start - 1] == diff[end])
			start--;
		while (start <= end)
			diff[start++]--;
	}
}

void bottomCase() {
	while (true) {
		int start = 0, end = 0;
		while (end < num - 1 && diff[end] >= diff[end + 1])
			end++;
		if (end == num - 1)
			return ;
		res++;
		start = end - 1;
		while (start > 0 && diff[start - 1] == diff[end])
			start--;
		while (start <= end)
			diff[start++]++;
	}
}

int	main()
{
	vector<int> src, dst;
	cin >> num;
	for (int i = 0; i < num; i++) {
		int input;
		cin >> input;
		src.push_back(input);
	}
	for (int i = 0; i < num; i++) {
		int input;
		cin >> input;
		dst.push_back(input);
	}
	for (int i = 0; i < num; i++)
		diff.push_back(src[i] - dst[i]);
	// 위로 뾰족한거
	topCase();
	// // 아래로 뾰족한거
	bottomCase();
	// 이제 다 같은 수로 바뀌었을테니 그 차이만큼 더해준다.
	res += abs(diff[0]);
	cout << res;
}

//1 2 3 3 2 1

diff가 음수끼리 양수끼리 그룹을 만들어서 그 그룹의 최솟값만큼 더해주는 로직으로 해결했다. 이런 비슷한 문제 어디서 풀어봤던거 같은데.. 그리디 문제좀 많이 풀어봐야겠다.

#include <iostream> // 성공!
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>

using namespace	std;
vector<int> diff;
int res = 0, num;

bool isAllZero(int start, int end) {
	for (int i = start; i <= end; i++)
		if (diff[i] != 0)
			return false;
	return true;
}

void drag(int start, int end) {
	int minEle, maxEle;

	minEle = *min_element(diff.begin() + start, diff.begin() + end + 1);
	maxEle = *max_element(diff.begin() + start, diff.begin() + end + 1);

	if (diff[start] > 0) { // 양수
		for (int i = start; i <= end; i++)
			diff[i] -= minEle;
		res += minEle;
	}
	else { // 음수
		for (int i = start; i <= end; i++)
			diff[i] -= maxEle;
		res -= maxEle;
	}
}

int	main()
{
	vector<int> src, dst;
	cin >> num;
	for (int i = 0; i < num; i++) {
		int input;
		cin >> input;
		src.push_back(input);
	}
	for (int i = 0; i < num; i++) {
		int input;
		cin >> input;
		dst.push_back(input);
	}
	for (int i = 0; i < num; i++)
		diff.push_back(src[i] - dst[i]);
	int start = 0, end = 0;
	while (start < num && isAllZero(start, num - 1) == false) {
		while (start < num && diff[start] == 0)
			start++;
		end = start;
		while (end + 1 < num && diff[start] * diff[end + 1] > 0) // 같은 부호
			end++;
		drag(start, end);
	}
	cout << res;
}