[C++] 백준 7570번: 줄 세우기 - DP

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

7570번: 줄 세우기

 

처음 문제를 읽었을 때 들었던 생각은 단순히 가장 긴 증가하는 부분 수열이었다.

그래서 열심히 LIS 코드를 짰는데, 이상하게 원하는 결과값이 출력이 되지 않았다.

그래서 임의로 사용한 예제

9
1 7 9 8 3 2 4 5 6

9
9 4 7 1 3 2 6 8 5

9
9 8 7 6 5 4 3 2 1

9
1 2 3 4 9 8 7 6 5

9
9 8 7 6 5 4 3 1 2

9
9 8 7 5 6 4 3 2 1

6
1 3 2 4 5 6

7 
2 1 4 3 5 6 7

8
2 1 4 3 8 5 6 7

8
4 2 3 1 8 5 6 7

 

그래서 알아낸 사실은 아래와 같다.

 

만약 학생이 6명이 있다면

오름차순으로 1 2 3 4 5 6으로 정렬이 되어야한다.

그런데 만약 입력이 1 2 4 3 6 5 로 들어온다면

답은 3이 출력되어야하지만 실제로는 2가 출력이 된다.

 

그 이유는 단순 증가하는 부분수열에 의해 1 2 3 5를 인식하여 4의 값이 저장되지만,

실제로는 1 2 3의 3 개이므로 증가함과 동시에 연속되어야함을 알 수 있었다.

 

그래서 어떻게 코드를 짜야하는지 고민하다가 처음했던 접근은 

i 번째 입력 값이 i - 1 번째 입력값 + 1 번째라면,

즉 i 번째 학생 번호가 i - 1번째 학생 번호 + 1 이라면 카운트를 증가시켜

카운트의 크기가 가장 큰 값이 곧 가장 긴 연속적인 증가하는 부분수열이라고 생각했다.

 

그래서 처음 짰던 코드

 

#include <iostream>
using namespace std;
int dp[1000001];
int main() {
    int n, cnt=1, ans=1; cin >> n;
    for(int i=0; i<n; i++){
        cin >> dp[i];
        if(i){
            if(dp[i]==dp[i-1]+1) cnt++;
            else cnt=1;
        }
        ans=max(cnt, ans);
    }
    cout << n-ans;
}

 

이렇게 코드를 짰더니 이상하게 1씩 차이가 나거나 동일하게 출력되었는데,

그 이유가 재배치가 필요 없는 인자가 최대 2개가 존재할 수 있기 때문이었다.

 

가령

5 2 3 4 1 6 7 이라고 한다면

2 3 4를 제외한 나머지 부분이 모두 재배치되어야하지만

 

1 5 2 3 4 6 7 이라고 한다면

5 6 7만 재배치해주면 되기 때문이다.

 

그래서 더욱 고민하던 중에

그냥 학생 번호를 입력 받고

해당 학생 번호 - 1번까지 얼마나 연속되었는지를 판단하는 방식으로 방향을 바꿨다.

 

쉽게 말해,

1 5 2 3 4 6 7

이렇게 주어진다면

dp[1] = 1

dp[5] = 1

dp[2] = 2 (1)

dp[3] = 3 (1, x, 2)

dp[4] = 4 (1, x, 2, 3)

dp[6] = 2 (x, 5, x, x, x)

dp[7] = 3 (x, 5, x, x, x, 6)

이므로 중간에 배치가 필요한 학생이 있더라도 가장 긴 연속하는 학생의 수를 구할 수 있으므로

위와 같은 코드를 짰다.

#include <iostream>
using namespace std;
int dp[1000001];
int main() {
    int n, ans=0, x; cin >> n;
    for(int i=0; i<n; i++){
        cin >> x;
        dp[x]=dp[x-1]+1;
        ans=max(ans, dp[x]);
    }
    cout << n-ans;
}