[SWEA] 3307 : 최장 증가 부분 수열

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=4 

SW Expert Academy

백준에서 풀었던 문젠데 약간 헤맸다.. 자존심 상해

DP 문제인데 해당 index까지의 최장길이를 저장하면 된다. 이 과정에서 실수함.

 

수열 {4, 2, 3, 1, 5, 6}을 예로 설명해보겠음.

1 ) 최소길이는 1이기 때문에 DP를 모두 1로 초기화해준다. DP는 해당 index까지의 최대길이를 저장해주는 배열.

 

2 ) 현재 탐색하는 수의 이전의 수들과 비교해줘야 하기 때문에 index 1부터 탐색해준다. 비교해주는 수들은 index 0부터 현재 index - 1까지. 이때 탐색하는 index의 DP에 더해줄 max라는 변수를 i가 증가할 때마다 0으로 초기화해준다.

 

3 )

     index = 1일 때 >> 2는 4보다 작기 때문에 max = 0, 이걸 DP[1]에 더해주면 그대로 DP[1]

 

     index = 2일 때 >> 3은 4보다 작기 때문에 max = 0, 2보다 크고 DP[1]가 max보다 크기 때문에 max = 1 >> DP[2]에 max(1)을 더해줘서 2. 

 

     index = 3일 때 >> 1은 4, 2, 3보다 작기 때문에 max가 그대로 0이어서 그대로 DP[3]

 

     index = 4일 때 >> 5는 4보다 크기 때문에 max = DP[0] (1), 2보다 큰데 DP[1]이 1이어서 max보다 크지 않으므로 max 갱신하지 않는다. 3보다 크고 DP[2]가 2로 max(1)보다 크기 때문에 max = DP[2]로 갱신해줌. 1보다 큰데 DP[3]이 1이어서 갱신해주지 않음.  DP[4] += max(2) 해서 DP[4] = 3.

 

     index = 5일 때 >> 6도 앞의 과정과 마찬가지로 진행하다 DP[4]의 3이 가장 크기 때문에 DP[5] += max(3) 해주면 DP[5]는 4이다.

 

4 ) 도출되는 DP값들을 최댓값을 결과값으로 갱신해주면서 진행하면 result의 값을 구할 수 있다.

 

내 코드

메모리 : 25948 KB

시간 : 155 ms

코드길이 : 1048 B

 

[내 코드]

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

public class Solution {
	static int N;
	static int[] num, DP;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			
			N = Integer.parseInt(br.readLine());
			num = new int[N];
			DP = new int[N];
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < N; i++) {
				num[i] = Integer.parseInt(st.nextToken());
				DP[i] = 1;
			}
			int result = 1;
			for(int i = 1; i < N; i++) {
				int max = 0;
				for(int j = 0; j < i; j++) {
					if(num[i] > num[j] && DP[j] > max) {
						max = DP[j];
					}
				}
				DP[i] += max;
				result = Math.max(DP[i], result);
				
			}

			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
}