[JAVA] 백준 11053번

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

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	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());

		int[] A = new int[N]; // 수열 A
		int[] dp = new int[N]; // 각 수열의 증가부분 최대 길이

		int result = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		for (int j = 0; j < N; j++) {
			dp[j] = 1;

			for (int k = 0; k < j; k++) {
				if (A[j] > A[k]) { // 현재 수와 이전까지의 수들 크기비교
					dp[j] = Math.max(dp[j], dp[k] + 1); // 각각의 최대크기 비교해서 가장큰값을 저장
				}
			}

		}

		for (int i = 0; i < N; i++) {
			result = Math.max(result, dp[i]);
		}

		bw.write(String.valueOf(result));
		bw.flush();
		bw.close();
	}

}

 

처음 문제에 접근한 방식

1. 각각의 수를 입력받고 이후에 큰 순자가 나올때마다 수열의 길이를 카운트함

2. ex) 1 8 2 4 6 의 경우 첫번째 1의 수열의 길이가 2로 나옴 1 -> 8  

3. 오답

 

정답을 맞춘 풀이방법

1. 각각의 수열의 최대값을 저장하는 dp배열을 선언 

2. n번째 수열의 최대 길이를 구할 경우 0 ~ n-1번째 보다 값이 크고, 저장된 dp값이 가장큰 경우를 계산해서 저장

3. 최대 길이를 출력