[코딩테스트 스터디/C++] 백준 18353번 병사 배치하기

1.문제 링크

https://www.acmicpc.net/problem/18353

2. 풀이 전 계획과 생각

• 다이나믹 프로그래밍 하기

3. 풀이

#include<iostream>
using namespace std;

int n;
int a[2001];
int d[2001];

int main(){
	// 입력  
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	// 가장 긴 감소하는 수열 구하기 
	for(int i=1;i<=n;i++){
        d[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]>a[i] && d[i]<d[j]+1)
                d[i]=d[j]+1;
        }
    }
    
    // 가장 긴 감소하는 수열 구하기  
    int max=d[1];
    for(int i=1;i<=n;i++)
		if(max<d[i]) max=d[i];
	
	// 답 출력  
	cout<<n-max;	
}

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)이라는 것이 있다. 백준에도 이문제가 있다.

이 문제를 기반으로 가장 긴 감소하는 부분 수열을 구했다.

이렇게 구한 수열수를 입력 배열 수 n에서 뺀다.

4. 풀이하면서 고민했던 점

• 가장 긴 증가하는 부분 수열 아이디어를 사용하는 것을 처음에 생각해내지 못함.

5. 문제를 풀고 알게된 개념 및 소감

• 다이나믹 프로그래밍에 개념에 대해 잘 알게됨