백준 23253번 자료구조는 정말 최고야 c++ 풀이

문제

찬우는 스택을 배운 뒤 자료구조 과목과 사랑에 빠지고 말았다.

자료구조 과목만을 바라보기로 다짐한 찬우는 나머지 과목의 교과서 �$N$권을 방 구석에 �$M$개의 더미로 아무렇게나 쌓아 두었다. 하지만 중간고사가 다가오자 더 이상 자료구조만 공부할 수는 없었고, 결국 찬우는 팽개쳤던 나머지 과목의 교과서를 정리하고 번호순으로 나열하려 한다.

 

 

출력

올바른 순서대로 교과서를 꺼낼 수 있다면 Yes를, 불가능하다면 No를 출력한다.

 

•  

예제 입력 1 복사

4 2
2
3 1
2
4 2

예제 출력 1 복사

Yes

 

위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다.

예제 입력 2 복사

5 2
3
3 5 1
2
4 2

예제 출력 2 복사

No

 

위 그림처럼 책이 쌓여 있으므로 어떻게 꺼내도 책 번호순으로 나열할 수 없다.

 

 

각 더미는 무조건 내림차순으로 정렬되어 있어야 한다. 그렇다면 Yes를 보장하고 아니라면 No이다. 이 규칙을 몰라서 헤메었다. 알면 굉장히 풀기가 쉬운 문제

 

#include <bits/stdc++.h>

using namespace std;


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

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        int temp = 987654321;

        for (int j = 0; j < k; j++) {
            int kk = 0;
            cin >> kk;
//            cout << temp << " " << kk << "\n";
            if (temp < kk) {
                cout << "No" << "\n";
                return 0;
            }
            temp = kk;
        }

    }
    cout << "Yes" << "\n";

    return 0;
}