์•Œ๊ณ ๋ฆฌ์ฆ˜

  • LIS๋ฅผ ๊ตฌํ•˜๊ณ , LIS๋ฅผ ๊ตฌ์„ฑํ•˜์ง€ ์•Š๋Š” ์š”์†Œ๋“ค๋งŒ ๋ฐฐ์น˜ํ•ด์ฃผ๋ฉด ๋จ

  • LIS๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋ก  n์ด ์ตœ๋Œ€ 200์ด๋‹ˆ O(n^2)์„ ์จ๋„ ์ถฉ๋ถ„ํ•จ

    • LIS ๊ตฌํ•˜๋Š” ์ฝ”๋“œ O(n^2)

      • ์ด์ „ ์š”์†Œ๋“ค ์ค‘์— ์ž๊ธฐ๋ณด๋‹ค ์ž‘์€ ๊ฒƒ ์ค‘, ๊ฐ€์žฅ ํฐ LIS๋ฅผ ๊ฐ€์ง„ ์š”์†Œ์— ์ด์–ด ๋ถ™์ž„
      for (int i = 1; i <= n; i++) {
      		save[i] = 1;
       
      		for (int j = 1; j < n; j++) {
      			if (nums[j] < nums[i])
      				save[i] = max(save[i], save[j] + 1);
      		}
      		ans = max(ans, save[i]);
      }
       

์ฝ”๋“œ

#include <iostream>
 
using namespace std;
 
 
int n, nums[220], ans, save[220];
int max(int a, int b) {
	return a > b ? a : b;
}
 
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> nums[i];
 
	for (int i = 1; i <= n; i++) {
		save[i] = 1;
 
		for (int j = 1; j < n; j++) {
			if (nums[j] < nums[i])
				save[i] = max(save[i], save[j] + 1);
		}
		ans = max(ans, save[i]);
	}
 
	cout << n - ans;
}