문제 바로가기

문제이해

6
10 30 10 20 20 10

감소하는 수열 중 가장 긴 수를 출력

10 30 10 20 20 10
이 예시에선 30-20-10이 된다.

7
1 3 1 2 2 1 8

여기선 맨 뒤의 8을 조심해야한다.
3- 2- 1
가장 긴 감소하는 수열의 수는 3이다.

사실 문제는 이해했으나 어떻게 접근해야하는지 감조차 오지않아 빠르게 다른사람들의 코드를 봤다.
그리고 손으로 직접 쓰며 이해했다.
숫자마다 max값과 i값을 따로 써보며 조건을 만족할때만 max값을 업데이트해주면 된다는 것을 알았다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class s2_11722 {
    static int n,arr[],answer[];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        answer = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        answer[0]=1;
        update();
    }
    public static void update(){


        for(int i=1;i<n;i++){
            int max=0;
            for(int j=0;j<i;j++){
                if(arr[j]>arr[i]){
                    max = Math.max(max,answer[j]);
                }
            }
            answer[i]=max+1;
        }
        Arrays.sort(answer); //첨에 이거 생각못해서 틀림
        System.out.println(answer[n-1]);
    }
}