백준 2374번 같은 수로 만들기 C++

출처 : https://www.acmicpc.net/problem/2374

 

가장 작은 수부터 인접한 수와 같게 만들어가면서 문제를 해결하였다. 

답을 int로 하면 오버플로우가 나기 때문에 long long을 사용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int n;
vector<int> v(1001);
ll ans = 0;

void Add(int index) {
	int val = v[index];
	int start = index;
	int end = index;
	int MIN = 1000000001;
	while (true) {
		start--;
		if (start <= 0) {
			start = 1;
			break;
		}
		if (v[start] != val) {
			MIN = min(MIN, v[start]);
			start++;
			break;
		}
	}
	while (true) {
		end++;
		if (end > n) {
			end = n;
			break;
		}
		if (v[end] != val) {
			MIN = min(MIN, v[end]);
			end--;
			break;
		}
	}
	for (int i = start; i <= end; i++) {
		v[i] = MIN;
	}
	ans += MIN - val;
}

void solve() {
	bool repeat = true;
	while (repeat) {
		repeat = false;
		int MIN = 1000000001;
		int lastVal = v[1];
		for (int i = 1; i <= n; i++) {
			if (lastVal != v[i]) {
				repeat = true;
				lastVal = v[i];
			}
			if (v[i] < MIN) MIN = v[i];
		}
		if (repeat) {
			for (int i = 1; i <= n; i++) {
				if (v[i] == MIN) {
					Add(i);
				}
			}
		}
	}
}

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	solve();
	cout << ans;
};