문제

문제 링크

어떻게 접근할 것인가

  • 이 문제은 디피로 접근할 수 있는 문제이다.
  • 각 순위에 올 수 있는 최솟값 계속 업데이트 한다.
  • 예제로 보면 1번 인덱스의 10은 1순위에 오는 최솟값이 되고 2번 인덱스의 20이 2번 인덱스에 오는 최소값이 된다.
  • 이렇게 해서 각 인덱스 값이 몇번째 위치의 최소값이 되는지 확인하고, 최소값들보다 모두 크다면 순위를 하나 더해준다.
  • 그리고 최종 순위를 출력한다.

코드

#include <cstdio>
int n, arr[1001], m[1001], cnt = 0, ans = 0;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
        for(int j = cnt; j >= 0; j--){
            if(m[j] < arr[i]){
                if(j == cnt)cnt ++;
                m[j + 1] = arr[i];
                break;
            }
        }
    }
    printf("%d", cnt);
}

느낀점

  • 아이디어가 좋아따!