[백준] 골드3 : (2879) 코딩은 예쁘게

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

 

가능한 많이 그룹을 묶어 탭을 편집해야 한다.

그룹을 묶는 조건은 나와 같은 편집 방법(추가 or 삭제)인 연속된 줄들만 묶을 수 있다.

개별적으로 남은 줄들은 어쩔 수 없이 남은 편집 횟수만큼 그대로 편집해줘야 한다.

 

따라서, 앞에서부터 자신의 줄이 올바를 때까지 다음 과정을 반복한다.

1. 나부터 시작해서 그룽으로 묶을 수 있는 마지막 줄의 위치까지 그룹으로 묶는다.
2. 그룹 내에서 가장 적은 편집 횟수로 올바르게 되는 줄의 편집 횟수를 찾는다.
   • 그룹을 다 같이 편집할 때, 하나라도 완성이 되면 그룹을 다시 재구성해야 하기 때문
3. 해당 편집 횟수만큼 그룹을 모두 편집한다.
   • 이러면 그룹 내에서 최소 한 개의 줄은 완성이 되므로 다시 그룹을 재구성해야 함.
4. 편집 횟수만큼 정답에 더한다.
5. 1~4번을 현재 줄이 완성될 때까지 반복한다.
6. 현재 줄이 완성되면, 다음 줄로 넘어가 1~5번을 반복한다.
   • 다만, 앞서 그룹을 통해 이미 줄이 완성됐을 수 있으므로, 이는 확인하여 넘어간다.

 

예시는 다음과 같다.

5
1 1 1 1 1
5 3 2 3 5

2 2 2 2 2
5 3 2 3 5
+1

3 3 2 2 2
5 3 2 3 5
+1

5 3 2 2 2
5 3 2 3 5
+2

5 3 2 3 3
5 3 2 3 5
+1

5 3 2 3 5
5 3 2 3 5
+2

answer = 7

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

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

	int N, Answer = 0;
	cin >> N;

	// {{ 현재 줄 탭 개수, 옵바른 줄 탭 개수 }, 탭 추가 or 삭제 Flag (true: 추가 / false: 삭제) } 
	vector<pair<pair<int, int>, bool>> Lines(N);

	// 현재 줄의 탭 개수 설정
	for (int i = 0; i < N; ++i)
		cin >> Lines[i].first.first;

	// 각 줄의 올바른 탭의 개수 설정 후, 현재 줄의  탭 개수와 비교하여 탭을 추가해야 하는지 삭제해야 하는지 Flag 설정
	for (int i = 0; i < N; ++i)
	{
		cin >> Lines[i].first.second;
		Lines[i].first.first - Lines[i].first.second > 0 ? Lines[i].second = true : Lines[i].second = false;
	}

	// 현재 탭의 위치
	int Cur = 0;
	for (Cur; Cur < N;)
	{
		// 이미 탭을 옵바르게 고친 줄은 패스 (이전 줄들로부터 그룹으로 묶여 이미 탭이 올바르게 설정됨)
		if (Lines[Cur].first.first == Lines[Cur].first.second) { Cur++; continue; }

		// 현재 탭의 탭 추가 or 삭제 여부
		bool Flag = Lines[Cur].second;

		// 현재 탭과 동일한 Flag를 가진 올바르지 않은 탭을 가진 줄들을 그룹으로 묶음
		int j = Cur;
		for (j; j < N; j++)
		{
			if (Lines[j].first.first == Lines[j].first.second) { break; }
			if (Lines[j].second != Flag) { break; }
		}

		// 그룹에서 가장 적은 편집 횟수를 구한다. (얘가 올바르게 고치면, 다시 그룹을 재구성 해야 하기 떄문)
		int Num = 987654321;
		for (int i = Cur; i < j; ++i)
		{
			if (Flag) Num = min(Num, Lines[i].first.first - Lines[i].first.second);
			else Num = min(Num, Lines[i].first.second - Lines[i].first.first);
		}

		// 해당 그룹의 줄들을 모두 편집 횟수만큼 추가 or 삭제
		for (int i = Cur; i < j; ++i)
			Flag ? Lines[i].first.first -= Num : Lines[i].first.first += Num;

		// 해당 그룹에서 편집한 횟수만큼 정답에 추가
		Answer += Num;
	}

	cout << Answer << "\n";
}