[SWEA] 최장 증가 부분 수열

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

DP를 사용해 각 자리까지의 최장 증가 수열을 저장한다.

 

nums는 입력받은 숫자 배열이고, dp는 각 자리까지의 최장 증가 수열을 저장하는 배열이다.

dp[0]은 제일 앞에 있는 값이므로 1로 두고 시작한다.

i = 1 부터 N - 1까지 접근해 각 자리의 최장 증가 수열을 구한다.

현재자리의 최장 증가 수열은 나의 앞에서 나보다 작은 애들 중의 최장 증가 수열 + 1이다.

예를 들어, nums가 1, 3, 2, 5, 4일 경우 dp[3]을 구하려면

인덱스 0부터 2까지 돌면서 나보다 작은 애들의 최장 증가 수열의 최댓값을 구한다.

nums[0], nums[1], num[2] 모두 5보다 작으므로, 얘들의 dp값을 비교하여 최댓값을 가져온다.

그 최댓값에 +1을 하면 dp[3]을 구할 수 있는 것이다.

 

코드

package swea;

// 최장 증가 부분 수열 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE&problemTitle=%EC%B5%9C%EC%9E%A5&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

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

public class SWEA_3307 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T;

		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			// input
			int N = Integer.parseInt(br.readLine());
			int nums[] = new int[N];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				nums[i] = Integer.parseInt(st.nextToken());
			}
			
			// solve
			int dp[] = new int[N];
			dp[0] = 1;
			for (int i = 1; i < N; i++) {
				int leftMax = 0;
				
				for (int j = i - 1; j >= 0; j--) {
					if (nums[j] <= nums[i]) {
						leftMax = Math.max(leftMax, dp[j]);
					}
				}
				
				dp[i] = leftMax + 1;
			}
			
			int max = 0;
			for (int i = 0; i < N; i++) {
				max = Math.max(max, dp[i]);
			}
			
			bw.write("#" + tc + " " + max + "\n");
		}

		bw.flush();
		bw.close();
	}

}