[BOJ] 같은수로 만들기 2374, 13146 (분할정복, 스택)

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

2374번: 같은 수로 만들기

풀이 방법 : 분할정복 (재귀), 스택

​

분할정복을 이용한 방법은 O(N^2)까지 나올 수 있어서, 13146에서 시간초과가 납니다.

하지만 stack을 이용한 풀이로 하면 O(N)으로 해결할 수 있습니다.

​

1. stack을 이용한 풀이

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

13146번: 같은 수로 만들기 2

이 문제를 해결하기 위해서는 이 풀이를 해야합니다.

​

스택을 바로 떠올리진 못했고, 힌트에 스택이라고 적혀있어서 스택을 생각했습니다.

처음에 저는 이렇게 생각을 했습니다. 1 2 3 6 을 해결하려면 어떻게 하면 될까요?

1,2,3,6에서 최솟값인 1을 찾아내서 6-1을 하면 답이 나오잖아요?

​

이걸 스택으로 어떻게 구현할까요? 순서대로 생각해봅시다.

최솟값을 찾아서 최댓값에서 빼버리면 되는거 아닐까요?

​

i = 0 일때

먼저 스택이 비어있으니까 맨 처음 값 arr[0]을 넣습니다.

stack = {1}

​

i = 1 일때

if(s.top() < arr[i]){ continue; }

뒤에가 더 크면 그냥 넘어갑니다.

stack = {1}

​

이런식으로 하면 맨 마지막에 stack엔 1밖에 없을 것 입니다.

그러면 마지막에 while(!s.empty())를 하면서 stack의 원소를 최댓값에서 빼면 되는게 아닐까요?

6-1 = 5. 오! 됩니다.

​

​

그러면

1 2 3 3 2 6 는 어떻게 해결할 수 있을까요?

위와 같은 방법으로 한다면 문제가 생깁니다.

​

스택에 1만 남아있어서 답이 5로 나옵니다. 하지만 정답은 6 입니다.

왜 이런 결과가 나올까요? 위의 방식으로하면 3,3,2에서 문제가 생깁니다. 마치 한번에 update가 되는것처럼 스택에 넣어놨지만, 실제로는 따로 add(4)를 호출해야 합니다. 따라서 약간의 수정이 필요합니다.

​

만약 3 2 1 이렇게 감소하는 경우에는 최솟값만 찾으면 되므로, 위에서 했던 방식처럼 하지만, 1,2,3 이렇게 올라가는 경우에는 미리 더하는 식으로 해결했습니다. (미리 더한다는건 1,2,3을 1 2 3 -> 2 2 3 -> 3 3 3 이렇게 만든다고 생각했습니다)

​

if(s.top() < arr[i]){ // 1,2,3 케이스

 cnt += arr[i] - s.top();

 s.pop(); s.push(t);

}else if(s.top() > arr[i]){ // 3,2,1 케이스 최댓값만 찾으면 됨

 s.pop(); s.push(t);

}

​

위의 식을

1 2 3 3 2 6 에 적용해 봅시다.

​

i = 0

stack = {1}

cnt = 0

​

i = 1

(s.top() < arr[i]) 이므로

stack = {2}

cnt = 1 // 2 2 로 만들어 줬다고 생각하면 됩니다.

​

i = 2

(s.top() < arr[i]) 이므로

stack = {3}

cnt = 2 // 3,3으로 만들어 줬다고 생각하면 됩니다

​

i = 3

아무일도 일어나지 않음

​

i = 4

(s.top() > arr[i]) 이므로 최솟값을 찾으러 갑니다.

stack = {2}

cnt = 2

​

i = 5

(s.top() < arr[i]) 이므로

stack = {6}

cnt = 6 이 됩니다.

​

이 과정에서 최댓값 6을 찾았고,

마지막 while(!s.empty()) 부분에서

6-6 = 0이 되기때문에

cnt는 결국 6으로 답이 나옵니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<int> s;
ll cnt;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    int max_num = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        max_num = max(max_num,t);
        if(s.empty()){
            s.push(t);
        }else{
            if(s.top() < t){
                cnt += t - s.top();
                s.pop(); s.push(t);
            }else if(s.top() > t){
                s.pop(); s.push(t);
            }
        }
    }

    while(!s.empty())
    {
        int num = s.top(); s.pop();
        cnt += max_num - num;
    }

    cout << cnt;
    return 0;
}

 

코드가 굉장히 간결한데, 속도는 정~~말 빠릅니다.

심지어 좀만 생각하면 배열도 필요하지 않습니다.

​

1억개여도 해결할 수 있습니다.

​

​

​

​

2. 분할정복을 이용한 풀이 (N^2)

-> 13146은 해결할 수 없지만, 분할정복의 느낌을 알게 됐습니다.

물론 재귀함수로 해도 되지만, 스택을 이용하면 어짜피 재귀 처럼 작동해서 스택을 이용해봤다.(연습겸)

물론 순서가 함수 호출처럼 가지는 않지만, 최종 결과는 동일합니다.

​

최댓값을 기준으로 양 옆으로 나눈다.

나눠진 배열에서 또 최댓값을 기준으로 양쪽으로 나누어가면서 실행한다.

설명을 잘 못하겠습니다. 예시를 봅시다.

​

​

1 2 1 1 5 3 을 예시로 들어보겠습니다.

func(start, end, max_val)

​

(0, 6, 5) 가 호출됩니다. (스택에 들어간다고 생각합시다)

​

int cur = 0,6에서의 최댓값입니다. 즉 5가 들어갑니다.

int idx = 5가 나오는 idx입니다. 5가 여러개면 맨 앞의 인덱스가 나옵니다. 즉 여기서는 4 입니다.

cur = 5, idx = 4 입니다.

그러면 이제 4를 기준으로 양쪽으로 나눕니다.

​

(0,4,5)가 호출됩니다.

{1,2,1,1}

cur = 2

idx = 1 입니다

​

(0,1,2) 가 호출됩니다.

cur = 1

idx = 0 입니다.

​

여기서

(1,1,1)이 호출되지만, (s.st>= s.en)에 의해서 그냥 사라집니다.

그러면 처음으로

​

cnt += s.val - cur이 나와서 ( 이전의 최댓값 - 현재의 최댓값)이 계산됩니다.

s.val은 2이고, cur은 1 입니다.

따라서 1이 더해집니다.

​

즉 여기서 {2,2,1,1,5,3} 이 되었다고 보면 됩니다.

​

이런식으로 2의 오른쪽 부분이 아래와 같이 호출이 됩니다.

(2,4,2}

여기서 또 1 까지 가서 1을 더해주고 이런 과정을 거칩니다.

​

직접 해보시면 와닿을것 같습니다. 퀵소트의 느낌입니다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct _tp{
    int st;
    int en;
    int val;
}tp;
stack<tp> st;
int arr[1005];
ll cnt;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int max_num = 0;
    int idx;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        if(max_num < arr[i])
        {
            max_num = arr[i];
            idx = i;
        }
    }

    tp t = {0,n,max_num};
    st.push(t);
    
    while(!st.empty())
    {
        tp s = st.top(); st.pop();
        if(s.st >= s.en) continue;
        int cur = *max_element(arr+s.st, arr+s.en);
        int idx = find(arr+s.st, arr+s.en,cur) - arr;
        if(s.st < idx){ t = {s.st,idx,cur}; st.push(t); }
        if(s.en > idx){ t = {idx+1,s.en,cur}; st.push(t); }
        cnt += s.val - cur;
    }

    cout << cnt;
    return 0;
}

감사합니다