HDOJ -- 1257 - 최소 차단 시스템

제목 설명: 한 나 라 는 적국 의 미사일 공격 을 방어 하기 위해 미사일 요격 시스템 을 발전 시 켰 다. 그러나 이 미사일 요격 시스템 은 첫 번 째 포탄 이 임의의 높이 에 도달 할 수 있 지만 이후 에는 모든 포탄 이 앞의 고 도 를 초과 해 서 는 안 된다 는 결함 이 있다. 어느 날 레이더 가 적국 의 미사일 습격 을 포착 했다. 이 시스템 은 아직 시험 단계 이기 때문이다.그래서 시스템 이 하나 밖 에 없 기 때문에 모든 미사일 을 막 을 수 없 을 수도 있 습 니 다. 어떻게 하 죠?시스템 을 몇 세트 더 만 들 지!말 하기는 쉬 운 데, 원 가 는?비용 은 큰 문제 입 니 다. 그래서 저 는 이곳 에 와 서 구 조 를 구 했 습 니 다. 최소 몇 개의 차단 시스템 이 필요 한 지 계산 해 주세요. 입력 설명: 몇 개의 데 이 터 를 입력 하 십시오. 각 조 의 데 이 터 는 미사일 총 개수 (정수), 미사일 이 이에 따라 날 아 오 는 높이 (레이더 가 제시 한 높 은 데 이 터 는 30000 이상 의 정수 가 아니 라 빈 칸 으로 구분 합 니 다) 를 포함 합 니 다.출력 설명: 각 조 의 데이터 출력 에 대응 하여 모든 미사일 을 차단 하려 면 적어도 몇 개의 미사일 요격 시스템 을 설치 해 야 합 니까? 입력: 8 389 207 155 300 299 170 158 65 출력:

#include
#include
#include
#include
using namespace std;

int a[100005];

int main(){
    int n,x;
    while(scanf("%d",&n)!=EOF){
        int ans = 0;
        int t = 0;
        for(int i = 0; i < n; i ++){
            bool flag = false;
            scanf("%d",&x);
            for(int i = 0;i < t; i++){
                if(x <= a[i]){
                    flag = true;
                    a[i] = x;
                    break;
                }
            }
            if(!flag){
                a[t++] = x;
                ans++;
            }
            sort(a,a + t);
        }
        cout<<ans<<endl;
    }
    return 0;
}