백준 2565 c++ "전깃줄" -PlusUltraCode-

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

 

[필자 사고]

LIS알고리즘을 떠올릴수 있으면 해결 point를 얻을 수 있었을 것이다.

있다가 나오는 index i의 의미는 i번째 이전에 있는 값들 중 자신보다 뒤에 있는 숫자들은 몇개인가?? 를 묻는 문제이다.

그래서 LIS문제는 매번 resultCount를 이용해 최대값을 갱싢해 줘야된다. 필자는 이 부분을 놓쳤다.

 

마지막 결과물에서 N-resultCount를 하면 답을 구할 수 있을 것이다. 

아래는 상세한 코드해설이다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 프로그램에서 사용할 데이터를 입력받고 초기화하는 역할을 한다.

• 먼저, N을 입력받아 주어진 데이터의 개수를 설정한다.
• dp 벡터와 arr 벡터를 크기 N+1로 설정하여 사용할 공간을 할당한다.
• 이후, N개의 (first, second) 형태의 데이터를 입력받아 arr 벡터에 저장한다.
• 마지막으로, arr 벡터를 first 값을 기준으로 오름차순 정렬하여 정렬된 데이터를 기반으로 이후 로직을 수행할 준비를 한다.

3. 증가하는 부분 수열을 이용한 동적 프로그래밍 (Game_Start 함수)

Game_Start() 함수는 주어진 데이터에서 특정 조건을 만족하는 최대 길이의 부분 수열을 찾고, 그 결과를 이용하여 답을 도출하는 역할을 한다.

• dp[i]는 i 번째 요소를 포함하는 증가하는 부분 수열의 최대 길이를 저장한다.
• dp[i]를 최소값인 1로 초기화하고, i보다 앞선 k 값들에 대해 arr[i].second > arr[k].second인 경우 dp[i] = max(dp[i], dp[k] + 1)을 수행한다.
• 최종적으로 resultCount에는 최대 길이의 부분 수열 길이가 저장되며, 전체 개수 N에서 이 길이를 빼서 제거해야 하는 최소 개수를 출력한다.

4. 프로그램 실행 (main 함수)

• Input() 함수를 호출하여 데이터를 입력받고 정렬한다.
• Game_Start() 함수를 호출하여 주어진 조건을 만족하는 부분 수열의 최대 길이를 계산하고, 제거해야 하는 최소 개수를 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 501
using namespace std;
typedef pair<int, int> Node;

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

bool cmp(Node a, Node b) {
	return a.first < b.first;
}

void Input() {
	cin >> N;
	dp.resize(N+1);
	arr.resize(N+1);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	sort(arr.begin() + 1, arr.end(), cmp);
}

void Game_Start() {
	int resultCount = 0;
	for (int i = 1; i <= N; i++) {
		dp[i] = 1;
		for (int k = 1; k < i; k++) {
			if (arr[i].second > arr[k].second) {
				dp[i] = max(dp[i], dp[k] + 1);
			}
		}
		resultCount = max(resultCount, dp[i]);
	}

	cout << N - resultCount;
}

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