[BOJ/C++] 2374 같은 수 만들기

그리디 알고리즘과 스택을 이용해서 문제를 해결할 수 있습니다.

재귀를 이용해서 문제를 풀어도 되지만 같은 수 만들기 2 문제에서 시간초과로 문제를 해결할 수 없습니다.

시간 복잡도 면에서 스택을 이용하는 것이 더 좋기 때문에 스택을 이용해서 문제를 해결해보겠습니다.

또한 입력의 최댓값이 10억이므로 int 대신 long long을 이용해 오버플로우를 해결할 수 있습니다.

예를 들어, 입력이 1 2 3 6 인 경우
2 2 3 6 / 3 3 3 6 / 4 4 4 6 / ... / 6 6 6 6 으로 입력이 오름차순인 경우엔 6-1 으로 총 5번의 Add를 진행하게 됩니다.

즉, 최댓값에서 최솟값을 빼면 값을 구할 수 있습니다.

하지만 입력이 1 2 3 2 6 의 경우

2 2 3 2 6 / 3 3 3 2 6 / 3 3 3 3 6 / ... / 6 6 6 6 6 으로 입력이 오름차순이 아닌 경우엔 최댓값 - 최솟값으로 해결할 수 없습니다.

1. stack.top() < 값 이라면 값 - stack.top()을 결과값에 더해주고 stack.pop(), stack.push(값)을 진행한다.
2. stack.top() > 값 이라면 stack.pop(), stack.push(값) 을 진행한다.
3. 최댓값을 계속해서 업데이트한다.
4. 같다면 패스해도 된다.

즉, 스택에는 내림차순 되는 값이 남아있게 되고 최댓값에서 스택에 남아있는 값을 빼준것을 마지막에 더해 해결할 수 있습니다.

// boj g4 2374
// 같은 수 만들기

#include <iostream>
#include<stack>


using namespace std;


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

    int N;
    long long result = 0;
    int max_num = 0;
    cin >> N;

    stack<int> s;

    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;;
        max_num = max(max_num, temp);
        if (s.empty()) {
            s.push(temp);
        }
        else {
            if (s.top() < temp) {
                result += temp - s.top();
                s.pop(); s.push(temp);
            }
            else if (s.top() > temp) {
                s.pop(); s.push(temp);
            }
        }
    }
   
	int num = s.top(); s.pop();
	result += max_num - num;
    
    cout << result;

    return 0;
}