[백준] 11053 - 가장 긴 증가하는 부분 수열 (Java)

[백준] 11053 - 가장 긴 증가하는 부분 수열 (Java)

문제

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

풀이/후기

처음에는 문제를 잘못읽고 풀어서 오답이 나왔다.

그리고 dp에 수열 중 선택한 값을 저장하는 방식으로 풀었는데

생각해보니까 수열의 크기를 구해야하기 때문에 dp에 부분 수열의 번호를 넣어서 풀어야 했다.

마지막에 dp[N-1]을 출력하면 당연히 답이 나와야한다고 생각했는데

N-1번째 숫자가 부분 수열의 멤버가 아닐 수 있기 때문에 그렇게 하면 안된다.

반복문을 한 번 더 돌려서 dp의 가장 큰 값을 뽑아서 출력한다.

코드

package DynamicProgramming;

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

public class Problem11053 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		str = new StringTokenizer(br.readLine());
		for (int i=0 ;i<N; i++) {
			arr[i] = Integer.parseInt(str.nextToken());
		}
		
		int[] dp = new int[N];
		
		for (int i=0; i<N; i++) {
			dp[i] = 1;
			
			for (int j=0; j <= i; j++) {
				if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
				}
			}
		}
		
		int max = Integer.MIN_VALUE;
		for (int i=0; i<N; i++) {
			max = dp[i] > max ? dp[i] : max;	//순열의 가장 마지막 순서를 탐색
		}
		System.out.println(max);	//dp[N-1]의 값으로 출력하면 오답 - 가장 마지막이 순열의 구성으로 결정되지 않을 수도 있기 때문
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/4a079943b0ae0b89dc04f017b1104da2776f23a9

참고

https://st-lab.tistory.com/137