[백준알고리즘] dp - 11053번 가장 긴 증가하는 부분 수열 문제

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

11053번: 가장 긴 증가하는 부분 수열

스터디 문제로 바이토닉 수열 문제가 있었는데,

그 문제를 풀기 전에 이 문제부터 풀어보면 좋을듯 하여 먼저 풀어보았다.

다행이도 어제 공부한걸 까먹진 않았는지 질 풀렸다.

수열과 같은 길이의 배열 dp[]를 선언하고 dp의 각 위치에 해당 위치까지 올수있는 가능한 수열의 길이값을 할당한다.

이중 가장 큰 길이값이 나오는걸 max변수에 저장하고 출력했다.

이중 for문과

if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
	dp[i] = dp[j] + 1;
}

이 부분이 핵심!

 

전체 풀이코드:

package week1;

import java.io.*;
import java.util.StringTokenizer;

public class PartialSequence {  //백준 11053번 가장 긴 증가 부분수열 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    //수열의 크기 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine());    //수열 입력받음
        int[] nums = new int[N];
        int[] dp = new int[N];  //N크기만큼의 Dp배열 생성, 여기에 각 수열값들 위치까지의 최대 부분수열 길이가 들어갈것임
        int max = 0;    //가장 긴 부분수열 길이
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;  //기본적으로 1이 들어간다(자기 자신 하나가 일단 원소니까 최소 길이는 모두 1씩)
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    /*증가하는 수열이 되어야 하니까 일단 j 원소의 크기가 i보다 작은지부터 확인,
                    dp[j]의 값, 즉 j번째 원소 다음에 i번째 원소가 오도록 수열을 만드는게 이득이면 dp[i] 갱신 */
                    dp[i] = dp[j] + 1;
                }
            }
            if(max < dp[i]) max = dp[i];    //안쪽For문에 뒀다가 바깥으로 뺐다(원소가 하나뿐이라면 안쪽For문 못도니까 이경우도 고려)
        }
        bw.write(Integer.toString(max));
        bw.flush();
        bw.close();
    }
}