이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 81 번째 글 입니다.
목차
실버1 : 동적계획법 문제이다.
max_element 최대한 쓰지 말자. 그리고 sizeof는 바이트수를 리턴해준다. 제발..ㅠㅠ
Code1
dp[n] = n번째 전깃줄을 포함한 상태로 가질 수 있는 최대 전깃줄 갯수
dp[n] = max(dp[1~n-1] + 1)
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int M = 0;
int map[501] = {0,};
int dp[501] = {0,};
int ans = -1;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
map[a] = b;
dp[a] = 1;
M = max(M, a);
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j < i; j++) {
if (map[i] < map[j] || dp[i] == 0) {
continue;
} else {
if (dp[i] < dp[j]+1) {
dp[i] = dp[j]+1;
}
}
}
}
for (int i = 0; i <= M; i++) {
ans = max(ans, dp[i]);
}
cout << N-ans << '\n';
return 0;
}
Code2
8 2 9 1 4 6 7 10
2 4 6 7 10
가장 긴 증가하는 부분 수열(LIS)로 풀 수도 있다. 예전에 고등학교 때 함수 개수 찾는 문제가 있다. 치역 부분에서 정의역 원소만큼의 개수를 뽑아주게되면 자연스레 원하는 함수가 만들어진다. 약간 그 느낌과 비슷한데, 해당 모양에서 답인 상황은 1 4 6 7 10 또는 2 4 6 7 10 과 같은 상황이다. 특징을 살펴보면 값이 증가하고 있다. 각각의 A 전봇대에서 가리키는 B 값들 중에서 증가하는 수열 중 가장 긴 것을 찾는다면, 그것이 최대 전깃줄의 개수일 것이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int dp[101];
vector<pair<int, int>> input;
bool compare(pair<int, int> a, pair<int, int> b){
return a.first < b.first;
}
int main(){
cin >> N;
input.push_back(make_pair(0, 0));
for (int i = 1; i <= N; i++) dp[i] = 1;
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
input.push_back(make_pair(a, b));
}
sort(input.begin(), input.end(), compare);
for (int i = 1; i <= N; i++) {
for (int j = 1; j < i; j++) {
if (input[i].second > input[j].second) {
dp[i] = max(dp[i], dp[j]+1);
}
}
}
int ans = -1;
for (int i = 1; i <= N; i++) {
ans = max(ans, dp[i]);
}
cout << N-ans << '\n';
return 0;
}