백준 11053 풀이

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

문제를 처음 보고 든 생각은

어라 이거 날먹 가능한 문제 아니야?

였다.

하지만 어림도 없지!!

그렇게 쉽게 문제가 나올리가 없다.

처음엔 수열이 아니라 부분 집합이라 생각하여 set으로 만들어 set의 사이즈를 출력해주는 단순하게 생각했다.

단순하게 생각하는 습관을 버려야하는데 잘 안 고쳐진다...

아무튼 당연히 틀렸고 다른 방법을 찾아야했다.

그 다음으로 생각한 방식은

증가하는 수열이니 이전 값보다 큰 값만 추가하여 수열을 만들어 size를 출력해주면 되지 않을까?

였다.

결론은 이것도 틀렸다. [1 5 2 3 4]를 입력할 경우 정답을 찾지 못한다.

결국 문제 분류를 확인했다.

DP였다!!!
이 문제가 DP로 풀린다고???

문제의 분류를 확인하고 다시 문제를 보니 단서가 보였다.

{10,20,10,30,20,50}이 예시로 나왔는데 가장 긴 길이의 수열을 만들 때 각 숫자가 가질 수 있는 수열의 길이는 {1,2,1,3,2,4}이다.

이를 통해 현재 숫자의 수열 길이는 자신보다 작은 값의 길이+1과 같다는 사실을 알 수 있었다.

이를 바탕으로 코드를 작성하여 문제를 해결했다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static boolean[] visited;
    static int[] p;
    static int[] ap;
    static int[][] arr;
    static int min = 1001;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String num = br.readLine();
        int n = Integer.parseInt(num);
        String line = br.readLine();
        String[] nums = line.split(" ");
        Integer[] array = new Integer[n];
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(nums[i]);
        }
        int idx = 0;
        Integer dp[] = new Integer[n];

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            int max = 1;
            //array의 값을 비교하여 현재 값이 이전 값보다 작고 dp[j]+1이 max값보다 크다면 갱신해준다
            for (int j = 0; j < i; j++) {
                if(array[j] < array[i]){
                    if(dp[j] +1 > max) {
                        max = dp[j] + 1;
                    }
                }
            }
            dp[i] = max;
        }

        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(dp));
        int max = list.stream().max(Integer::compare).orElse(-1);

        bw.write(Integer.toString(max));
        br.close();
        bw.close();
    }
}

문제의 유형을 빠르게 파악하지 못해 많이 헤맸다... ㅠㅠ