백준 3015번 :오아시스 재결합

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

3015번: 오아시스 재결합

 

이 문제는 처음에 그냥 다 세면 되지 않을 까 라고 쉽게 생각했으나 시간복잡도가 어마무시해지는걸 깨닫고 바로 패스했다.

즉 반복문은 한번 써 한바퀴만 돌면서 값을 알아내야 했다. 스택의 개념을 적용 해서 값을 스택에 넣고 다음 값이 스택 값보다 클 경우에 스택에 있는 값은 다음 값보다 뒤에 있는 것은 아예 볼 수 없으므로 스택에서 빼주며 1을 더해준다.

이렇게 구현을 하다보면 쉽게 구현이 가능하다.

근데 역시나 쉽지 않다... 괜히 골드1문제가 아닌듯//

 

요점은 키가 같은 사람이 있을 때 이다. 처음에 나는 도대체 무슨 문제가 있나 라고 엄청 오랫동안 생각을 했다.(결국 답지봄 ㅜㅜ)

근데 키가 같은 사람들은 서로 볼수 있다.

어떤 뜻이면

첫번쨰)

키가 4 4 4 가 있다.        3쌍

그리고 3 2 1 이 있다.       2쌍

즉 그냥 A와 B보다 키가 큰 사람만 없으면 볼수 있다라는 조건만 적용하기에는 저런 변수가 존재 한다는 것이다.(구현에 문제가 있음)

두번째)

그4 4 4 7 일 떄 키가 4인 사람이 모두 7을 볼 수 있다. 

또 3 2 1 7 일떄 3 2 1 인 사람이 모두 7을 볼 수 있다.

여기서 문제점은 같을 때 와 작을 떄 의 조건을 동일시 하고 구현하면 두번쨰는 잘 작동하지만 첫번째는 작동하지 않는다.

즉 같을 때를 다르게 조건을 부여해야하고

같은 사람을 pair을 이용해서 연속으로 나오면 (4,1) (4,2) (4,3) 이런식으로 몇번째 사람인지 구해야 한다.

왜 이렇게 하냐면 수학적 접근이 필요한데 우리는 저 같은 사람이 연속으로 나오면 second 값을 더하면서 갈 것이다.

즉 (1+2) 3쌍 이렇게 말이다. 이게 성립이 되는 이유는 n명에서 r명을 고르는 것은 n​Cr 이고 이것은 (1+2+...+n-1)이랑 같다  

사실 이렇게 말해도 코드를 안보면 이해가 안간다 코드랑 같이 보자

(이거 못풀고 답을 봐도 이해못해서 엄청 헤맸네..ㅠ)

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin >>v[i];
    } 
    long long cnt=0;
    stack<pair<int,int>> s;
    for(int i=0;i<n;i++){
        pair<int,int> p={v[i],1};
        while(!s.empty()){
            if(s.top().first<=v[i]){                //v[i]값이 스택 보다 크면
                cnt+=(long long)s.top().second;       //더하기
                if(s.top().first==v[i]){                    //값이 같을때
                    p.second+=s.top().second;
                }
                s.pop();                            //스택에는 자신보다 큰 값이 나오지 않는 이상 스택에 저장 이유는 다른 값을 볼 가능성이 있기 때문에
            }else{
                break;
            }
        }
        
        if(!s.empty()){          //스택에 있는 값과 쌍을 이룰수 있으므로 비워있지 않으면 1 더하기
            cnt+=1ll;
        }
        s.push(p);
    }
    cout << cnt;
}