😄 최근에 비슷한 문제를 풀어서 그런가. 보고 끄적끄적하다가 어떻게 풀어야할지 딱 알아냈다.
가장 큰 증가하는 부분수열
이다. Dynamic Programming
으로 풀어줘야 한다.for (int i = 0; i < N; i++)
{
dp[i] = 1;
for (int j = i - 1; j >= 0; j--)
{
if(v[i] > v[j] && dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
}
}
result = max(result, dp[i]);
}
dp[i]
는 1로 초기화해줘야 자기보다 앞에있는 번호들을 탐색하다가 작은수가 존재하지 않아도 1로 설정이 가능하다.v[i] > v[j]
: 자기 자신이 앞에 있는 수보다 커야 증가하는 수열dp[i] < dp[j] + 1
: 자기 자신의 dp 수량보다 앞 수의 dp 수량+1이 더 많아야 가장 큰 증가하는 수열!!#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;
#define endl "\n"
int N, result = 0;
vector<int> v;
int dp[201];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N;i++)
{
int num;
cin >> num;
v.push_back(num);
}
for (int i = 0; i < N; i++)
{
dp[i] = 1;
for (int j = i - 1; j >= 0; j--)
{
if(v[i] > v[j] && dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
}
}
result = max(result, dp[i]);
}
cout << N - result << endl;
}
😜 해결방법만 알면 금방 풀어낼 수 있는 문제다. 그래서 그런지 정답률이 높다!! 필자는 운이 좋게도?? 보자마자 어떻게 풀어야할지 감을 잡아서 빠르게 풀어낼 수 있었다.