백준 11053 - 가장 긴 증가하는 부분 수열

 

[접근방법]

DP 문제인 것 같다!

Bottom-up(반복문)👌 / Top-Down(재귀)

 

 

예시를 잘 생각해 내야 된다.. 문제가 짧다고 후딱 읽고 풀면! 틀린다. 그리하여

[생각해본 예시]

9
3 1 2 3 4 5 6 4 5
👉 ans : 6

 

[구현]

위 예시를 바탕으로 두려움에 떨며 이중 for문을 만들어 보았다.

단순히 이전 인덱스 값을 비교하면 원하는 값이 나오지 않을 것 같았다.

 

** DP를 모조리 1로 채워줬다. input으로 5, 5, 5, 5 이 들어가도 1을 반환해야 하기 때문에

 

1st for :  i는 두 번째 원소부터 마지막까지 돌면서

2nd for : j를  i 이전 원소들로 지정해 자기자신(i)과 비교한다

 

▶ 만약 j번째 원소(arr[j])가 i번째 원소(arr[i])보다 작다면 (증가 수열 만족),

DP[j]+1(j번째 원소 - i번째 원소를 연결하는 수열)과 현재 DP[i]를 비교해서 큰 값을 DP[i]에 저장해준다.

👉 DP의 각 원소에 최대한 긴 수열을 저장하고야 말겠다

 

DP에서 가장 큰 값을 리턴하면 끝

 

[소스코드]

package baekjoon;

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

//가장 긴 증가하는 부분 수열
public class N11053 {

    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(buf.readLine());
        StringTokenizer tok = new StringTokenizer(buf.readLine());
        int[] arr = new int[cnt];
        int[] dp = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            arr[i] = Integer.parseInt(tok.nextToken());
        }
        Arrays.fill(dp,1);
        for (int i = 1; i < cnt; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        int max = Arrays.stream(dp).max().getAsInt();
        System.out.println(max);
    }
}

[제출]