반응형
728x170
증가수열과 비슷하다.
여기서 전깃줄이 겹칠 때 어떨 때 겹칠까 생각해보면 된다.
https://www.acmicpc.net/problem/2565
#맞은 풀이
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//A가 내가 고르는 것 B가 결과라고 해보자
//내가 고른 것이 이전에 고른 것의 결과보다 작아선 안된다.
//다음 것은 내가 고른 것의 결과보다 항상 커야한다.
//1번줄을 연결해서 2번줄의 결과를 얻었다면
//2번줄을 연결했을 때 2번보다 작은 결과를 얻어서는 안된다.
//내가 순서대로 고르고 결과만 위의 조건에 맞게 하면 되겠다.
//-> 전깃줄 순서대로 정렬
//전깃줄을 삭제하는 방법이 아닌 최대의 전깃줄 연결 방법
//-> 최대 5개의 전깃줄을 연결할 수 있다 == 설치한 전깃줄 - 최소로 제거하는 전깃줄
int N;
vector <pair<int, int>> vec;
int arr[101];
int dp[101]; //결괏값들의 최대 부분 증가 수열
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
int from, to;
cin >> from >> to;
vec.push_back({ from, to });
}
//from 기준으로 오름차순 정렬
sort(vec.begin(), vec.end());
//dp초기화
fill(dp, dp + 101, 1); //자기 자신을 항상 포함하므로 1의 최소 크기를 가짐
//결괏값들을 내가 고른 전깃줄의 오름차순으로 배열에 집어넣음
int cnt = 1;
for (auto x : vec) {
arr[cnt++] = x.second;
}
int ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
cout << N - ans;
return 0;
}
사실 겹친다는 것의 의미는
내가 이전에 결과보다 이번의 결과가 더 작다는 말이다.
즉, 겹치지 않으려면 이전의 결과보다 커야 한다는 말이다(중복이 안되니까)
이 말이 알고보니 결괏값이 증가수열로 나와야 한다는 의미고
최대 증가 부분 수열을 구하라는 의미였다.
문제 속에서 이것을 알아냈다면 쉽게 풀 수 있었겠지만..
저렇게까지 바로 이해하기는 쉽지 않다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 5557번, 1학년 : C++ [CPP] (0) | 2022.01.01 |
---|---|
백준, BOJ, 1309번, 동물원 : C++ [CPP] (0) | 2021.12.31 |
백준, BOJ, 11054번, 가장 긴 바이토닉 부분 수열 : C++ [CPP] (0) | 2021.12.31 |
백준, BOJ, 11048번, 이동하기 : C++ [CPP] (0) | 2021.12.29 |
백준, BOJ, 11053번, 가장 긴 증가하는 부분 수열 : C++ [CPP] (0) | 2021.12.29 |