글 읽기 - 2532 먹이사슬 도움 좀 주세요 ㅠㅠ

mrcamel 9년 전 0

자주 보이던 스택 문제 같아서 쉬울줄 알았는데..

스택에서 빼는데 문제가 있나요?

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

#define in cin
#define out cout
#define isin(a, b, c) ( (a<=c)&&(c<=b) )
#define PII pair<int, int>

int cmp(const PII &a, const PII &b) //비교 함수
{
    if(a.first != b.first) return a.first < b.first;
    else return a.second > b.second;
}

int main()
{
    int n; in >> n;
    vector< PII > v;
    for(int i=0; i<n; i++)
    {
        int i1, i2, i3; in >> i1 >> i2 >> i3; // 번호(의미없음), 왼쪽, 오른쪽
        v.push_back(make_pair(i2, i3));
    } sort(v.begin(), v.end(), cmp); // 왼쪽을 기준으로 오름차순 정렬, 같으면 길이가 긴 것을 앞으로

    PII q[500001]; int qi = 0; //스택
    q[qi] = make_pair(-1, 1000000001);
    
    int res = 0; 
    for(int i=0; i<n; i++)
    {
        PII pp = v[i]; //새로 넣을꺼
        PII qq = q[qi]; //스택 맨위에 있는거
        if( ((qq.first < pp.first) && (qq.second > pp.second)) || //조건 만족시 스택에 추가
           ((qq.first == pp.first) && (qq.second > pp.second)) ||
           ((qq.first < pp.first) && (qq.second == pp.second)) )
        {
            qi++; q[qi] = pp; // 스택에 추가
        }
        else
        {
            while(qi > 0) //조건을 만족 할때까지 스택 맨위부터 하나씩 지움
            {
                qq = q[qi]; 
                if( ((qq.first < pp.first) && (qq.second > pp.second)) || 
                   ((qq.first == pp.first) && (qq.second > pp.second)) || 
                   ((qq.first < pp.first) && (qq.second == pp.second)) )
                {
                    break;
                }
                qi--; // 스택에서 제거
            }
            qi++; q[qi] = pp; // 스택에 추가
        }

        if(res < qi) res = qi;
    } out << res << endl;

    return 0;
}

yukariko 9년 전 1

1 0 10

2 0 5

3 3 10

4 3 4

5 2 5

위 입력에 대해 3을 리턴합니다.

정답은 4가 되야 맞습니다. 1 > 2 > 5> 4 로요.

mrcamel 9년 전 0

매번 도움주셔서 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2532 먹이사슬 도움 좀 주세요 ㅠㅠ

mrcamel 9년 전 0

yukariko 9년 전 1

mrcamel 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말