백준 2631 c++ "줄세우기" -PlusUltraCode-

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

 

[필자 사고]

가장 큰 증가하는 수열 관련 문제이다.

다만 LIS를 통해 구한 값에 N- LIS 아이디어를 떠오르는건 쉽지 않았을 것 같다.

필자는 처음에 바로 아이디어가 떠오르지 않았고 
작은 수부터 차근차근 해보니 혹시 이러지 않을까 하는 직감..?? 으로 해보니 일관된 답들이 나올 수 있어서 
알고리즘을 작성했따.

[코드 해설]

1. 입력 처리 (Input 함수)

먼저, 프로그램은 사용자로부터 수열의 크기를 입력받는다. 이 크기를 기준으로 두 개의 벡터를 선언하는데, 하나는 실제 수열을 저장하는 arr 벡터이며, 다른 하나는 각 원소를 마지막으로 하는 최장 증가 부분 수열의 길이를 저장하는 dp 벡터이다.

이 dp 벡터는 모든 원소를 최소한 자기 자신 하나만 포함하는 부분 수열로 간주하여 초기에 모든 값을 1로 설정한다. 그런 다음, 입력받은 수열을 arr 벡터에 저장한다.

---

2. 동적 프로그래밍을 이용한 LIS 계산 (Game_Start 함수)

입력된 수열을 바탕으로 이중 루프를 활용하여 LIS를 계산한다.

• i는 현재 고려하는 원소를 의미하며, j는 i보다 앞에 있는 원소들을 가리킨다.
• arr[i]가 arr[j]보다 크다면, 즉 증가하는 관계가 성립하면, arr[i]는 arr[j] 뒤에 올 수 있다.
• 따라서 dp[i] 값을 dp[j] + 1과 비교하여 더 큰 값으로 갱신한다.
• 이렇게 하면 dp[i]는 arr[i]를 마지막 원소로 하는 LIS의 최댓값을 가지게 된다.

이 과정을 모든 원소에 대해 반복하면, dp 배열에는 각 위치에서의 LIS 길이가 저장된다.

마지막으로 dp 배열에서 가장 큰 값을 찾으면, 전체 수열에서 가장 긴 증가하는 부분 수열의 길이를 얻을 수 있다. 이를 전체 길이 N에서 빼면 제거해야 하는 최소 원소의 개수를 구할 수 있다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int N;
vector<int> dp;
vector<int> arr;

void Input() {
	cin >> N;
	dp.resize(N + 1,1);
	arr.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void Game_Start() {
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	cout << N - *max_element(dp.begin() + 1, dp.end());
}

int main(void) {
	Input();
	Game_Start();
}