백준 18353 C++

문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

가장 긴 감소하는 부분 수열?

수열 A가 {1,6,5,7,2,4}가 있을 떄 가장 긴 감소하는 부분 수열을 구하려 한다면

1일때는 숫자가 1개뿐이라 가장 긴 감소하는 부분 수열 → 1이다.

6일때는 {1}을 비교했을 때 1 < 6 이므로 가장 긴 감소하는 부분 수열은 마찬가지로 1이다.

5일떄는 {1,6}를 비교해서 {6,5}가 가장 긴 감소하는 부분 수열이 된다.

7일떄는 마찬가지로 {6,5}이므로 길이가 2이고,

2일떄는 {6,5,2}

4일떄는 {6,5,4}로 길이가 3이된다

for(int i = 0;i<n;i++){
	for(int j = 0;j<i;j++){
			if(arr[i] < arr[j] && dp[j] + 1 > dp[i]){
					dp[i] = dp[j] + 1;
	}
}

 

1	6	5	7	2	4
1	1	1	1	1	1

 

i가 2일때, j는 0,1을 지나게 되는데,

j가 0일떄는

arr[i] = 5, arr[j] = 1 이때, arr[i] > arr[j] ( 5 > 1 )이므로 아무 변화 없음

j가 1일때는

arr[i] = 5, arr[j] = 6. 이때 arr[i] < arr[j] ( 5 < 6 ) 이면서 dp[j] + 1 > dp[i]이므로 dp[i] = dp[j] + 1

1	6	5	7	2	4
1	1	2	2	3	3

예제에서 가장 긴 감소하는 부분 수열

→

원래의 수열 {15,11,4,8,5,2,4}의 가장 긴 감소하는 부분 수열은

{15,11,8,5,4}가 되고 길이는 5이다.

남아있는 병사 수를 최대로 하면서 내림차순을 유지하라면 가장 긴 감소하는 부분 수열이 정답이 되고, 전체 병사 - 가장 긴 감소하는 부분 수열의 길이 가 열외되는 병사의 수이다.

 

#include <iostream>
using namespace std;
int min(int a,int b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}
int main(void){
    int n;
    cin >> n;
    int arr[2000];
    int dp[2000];
    
    for(int i = 0;i<n;i++){
        cin >> arr[i];
        dp[i] = 1;
    }
    
    int max = -1;
    
    for(int i = 0;i<n;i++){
        for(int j = 0;j<i;j++){
            if(arr[i] < arr[j] && dp[j] + 1 > dp[i]){
                dp[i] = dp[j] + 1;
            }
        }
    }
    
    for(int i = 0;i<n;i++){
        if(dp[i] > max){
            max = dp[i];
        }
    }
    
    cout << n-max;
}