[백준/C++] 2631번 줄세우기 (LCS)

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

2631번: 줄세우기

1. 문제 접근

아이고 이거 문제 태그 없었으면 큐로 줄 빙글빙글 돌릴뻔 했습니다.
역시 DP는 바로바로 문제를 파악할 수 있는 능력이 있어야 할 것 같아요.

여러 학생이 서있고, 최소한의 자리 바꿈으로 1~N까지 줄을 세우려면요,
최대한 많은 학생을 제자리에 고정시켜놓아야 합니다.

예를 들어, 학생들이 다음과 같이 줄을 서있다고 합시다.

1 2 4 5 3 6 7

1번, 2번, 4번, 5번, 6번, 7번을 고정시켜놓고, 오름차순의 순리에 거스르는 3번 학생만 자리를 옮기면 돼서 답은 1입니다.

그럼 예제의 경우에는 어떨까요? 예제는 다음과 같이 서있습니다.

 3 7 5 2 6 1 4

3번, 5번, 6번학생을 고정시켜놓고, 오름차순의 순리에 거스르는 1, 2, 4, 7번 학생만 자리를 옮기면 돼서 답은 4입니다.

어라, 뭔가 감이 오시나요??

이 문제에서 가장 중요한 점은,
오름차순이 제~~~~일 길게 가는 학생의 번호들을 골라야 한다는 것입니다. 당연하게도, 오름차순만 유지되면 중간에 다른 학생들이 들어와도 괜찮아요. 그게 문제에서 의도한 내용이니까요.

예를 들어서 학생들이 다음과 같이 서있다고 합시다.

4 2 3 5 6 7 1

0번째 인덱스부터 가장 긴 학생들의 번호는요, 2, 3, 5, 6, 7입니다.
그런데 "1차원 DP에 오름차순으로 학생이 들어오면 이전 인덱스에서 +1을 해줘야지!!" 라고 생각하신다면, 아마도 4, 5, 6, 7을 고르게 되실 것입니다. 중간에 4보다 작은 수가 등장해도, 그 작은 수를 기준으로 DP를 다시 시작하는 기준은 1차원에선 많이 어려울 수도 있어요. 왜냐면 그 작은 수가 정말로 최장의 오름차순 순열을 찾아내리라는 보장이 없으니까 말이죠!!

예를 들어(4, 5, 6, 7, 1, 2)의 경우 -> 1,2를 고르는 것 보다 4, 5, 6, 7을 고르는 것이 훨씬 더 긴 부분 오름차순이니까요.

그래서 저는 LCS알고리즘을 적용시켰습니다.

2. LCS알고리즘

LCS알고리즘은 최장 공통 부분 수열을 찾아내는 알고리즘입니다.

이 블로그보다 더 잘 설명할 자신이 없습니다. 정독하고 와주시면 될 것 같습니다.
https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

우리는 문자열이 아닌 뒤죽박죽인 숫자를 오름차순 기준 가장 긴 부분 수열을 찾아야하므로, 다음과 같은 2차원 배열을 조성했습니다.

위의 블로그를 보고 오시면요, 문제에서 주어진 예제인 (3, 7, 5, 2, 6, 1, 4)수열이 최종적으로 다음과 같은 2차원 배열로 나타난다는 것을 아실 수 있을 거에요.

그럼 마지막으로 오른쪽 최 하단의 숫자 3이 가장 길게 오름차순으로 서있는 학생들이 숫자이므로, 자리를 바꿔야할 학생들의 최솟값은 
7-3 = 4명입니다.

정답 코드

//
//  줄세우기.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2023/01/10.
//

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

int lcs[205][205];

void print_array(int n, int m){
    cout<<"\n==========================\n";
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout<<lcs[i][j]<<" ";
        }
        cout<<endl;
    }
    
    cout<<"\n==========================\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin>>n;
    
    for(int i=2; i<=n+1; i++){
        cin>>lcs[i][0];
        lcs[0][i] = i-1;
    }
    
    for(int i=2; i<=n+2; i++){
        for(int j=2; j<=n+2; j++){
            if(lcs[i][0] == lcs[0][j]) lcs[i][j] = lcs[i-1][j-1] + 1;
            else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
        }
    }
    
    cout<<n - lcs[n+1][n+1];
    
    return 0;
}

* print_array(n+2, n+2)를 코드 중간에 삽입해서 lcs배열의 변화를 확인해보세요.