[BOJ 7570 // C++] 줄 세우기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7570번 문제인 줄 세우기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/7570

7570번: 줄 세우기

이 문제는 5 2 3 1 4 6에서의 "2 3 4"와 같이 1씩 증가하는 부분수열의 길이의 최댓값을 찾는 문제로 볼 수 있다.

1씩 증가하는 최장 부분수열에 해당하는 아이들을 제외한 다른 아이들을 순서에 맞춰 앞뒤로 이동시켜주면 되기 때문이다.

 

단순히 증가하는 부분수열만 만족하면 안 되는 이유는 아이들을 항상 맨 앞이나 맨 뒤로만 보낼 수 있기 때문이다. 예를 들어, 2 1 3 5 4 에서 1과 3, 3과 5 사이에 각각 2번 아이와 4번 아이가 한번에 들어갈 수 없기 때문이다. (답은 3번이다.)

 

글쓴이는 지금 서있는 아이들을 한번씩 보면서 이 아이 앞쪽에 앞번호 아이가 있었는지 확인한 배열을 저장한 뒤, 연속해서 앞번호 아이가 서있는 구간을 찾는 식으로 문제를 해결했다.

 

예를 들어, 10명의 아이가 1 3 2 4 6 8 5 7 10 9 와 같이 서있는 상황을 생각해보자.

각 아이 앞쪽에 앞번호 아이가 있는 아이는 2 4 5 7 9 번 아이다. 이 때, 4 5 가 가장 길게 붙어있는 부분이고, 4 앞에 있는 3번 아이까지 고려하면, 이 수열에서 1씩 증가하는 부분수열 길이의 최댓값은 3이 된다.

 

답을 낼 때 구한 최댓값을 전체 아이 수에서 빼는 것을 잊지 말자. 항상 문제가 요구하는 것을 제출해야 한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

bool kids[1000001];
bool kidschk[1000001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int x;
    for (int i = 1; i <= n;i++) { // 먼저 앞번호 아이가 들어왔다면 기록
        cin >> x;
        if (kidschk[x - 1]) kids[x] = true;
        kidschk[x] = true;
    }
    int cnt = 0, mx = 0;
    for (int i = 1;i <= n;i++) { //연속해서 앞번호아이가 있는 최대길이 구하기
        if (kids[i]) {
            cnt++;
            if (mx < cnt) mx = cnt;
        }
        else cnt = 0;
    }
    cout << n-(mx+1);

    return 0;
}