백준 18353 _ 병사 배치하기

www.acmicpc.net/problem/18353

18353번: 병사 배치하기

---

✨ 내 소스 코드

#include<iostream>
#include <string>
#include<algorithm>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int dp[2001];
	int seq[2001];
	int N, max_dp = 0;
    
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> seq[i];
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (seq[j] > seq[i] && dp[j] + 1 > dp[i] && max_dp<dp[j]) {
				max_dp = dp[j];
			}
		}
		dp[i] += max_dp;
		max_dp = 0;
	}

	for (int i = 0; i < N; i++) {
		if (dp[i] > max_dp) {
			max_dp = dp[i];
		}
	}
    
	cout << N-max_dp;

	return 0;
}

 

🙏 문제 풀이

가장 긴 감소하는 부분 수열(www.acmicpc.net/problem/11722) 문제의 응용 버전이었다

 

전투력이 감소하는 가장 긴 부분 수열의 길이를 찾아서 전체 길이에다가 빼주면

열외해야되는 병사의 수가 나오게 된다

 

자세한 문제 풀이는 가장 긴 감소하는 부분 수열(rosyhuedoyou.tistory.com/46) 참고

 

 

⭐ 문제 풀이 결과