[C++] 백준 2374번: 같은 수로 만들기 - Stack

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

2374번: 같은 수로 만들기

 

배열의 원소를 1씩 더하는데, 인접한 수가 같으면 해당 원소도 1이 더해진다.

최종적으로 모든 원소가 같아지기 위한 연산 횟수의 최솟값을 구하는 문제이다.

 

해당 문제는 먼저 greedy로 접근을 했었다. 

최댓값을 알아내고, 결국 모든 수는 최댓값을 향하므로 최댓값 양측에 존재하는 최솟값들의 연산 횟수를 계산했었다.

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
using ll=long long;
vector<ll>v;
stack<ll>s;
int main(){
    long long x, n, ans=0, ma=0, mi; cin >> n;
    for(int i=0; i<n; i++){
        cin >> x;
        if(v.empty() || v.back()!=x){
            v.push_back(x);
            ma=max(ma, v.back());
        }
    }
    mi=ma;
    for(int i=0; i<n; i++){
        mi=min(mi,v[i]);
        if(v[i]==ma){
            ans+=v[i]-mi;
            mi=ma;
        }
    }
    ans+=ma-mi;
    cout << ans;
}

 

그런데 여기서 발생한 문제점은

4
1 3 2 7

위의 예제처럼 1 3 2 7이 주어졌을 경우 1의 경우만 계산하여 6을 출력하겠지만,

실제로는 2도 3으로 맞춰준 후 7로 계산해야하므로 7이 출력되어야한다.

 

그래서 스택을 이용하여 문제를 다시 접근했다.

 

스택의 top과 현재 값을 비교하면서 top이 더 큰 경우 stack에 원소를 집어넣고,

더 작은 경우 현재 top과 비교하여 ans를 차이만큼 더해주었다.

그리고 top이 현재 원소보다 작아질때까지 pop을 해주었다. 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
using ll=long long;
vector<ll>v;
stack<ll>s;
int main(){
    long long x, n, ans=0; cin >> n;
    for(int i=0; i<n; i++){
        cin >> x;
        if(v.empty() || v.back()!=x) v.push_back(x);
   }
    for(int i=0; i<v.size(); i++){
        if(!s.empty() && s.top()<v[i]){
            ans+=v[i]-s.top();
            while(!s.empty() && s.top()<v[i]) s.pop();
        }
        s.push(v[i]);
    }
    while(s.size()>1){
        x=s.top(); s.pop();
        ans+=s.top()-x;
    }
    cout << ans;
}