[SW expert Academy] SWEA 3307번 최장 증가 부분 수열 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [SW expert Academy] SWEA 3307번 최장 증가 부분 수열 자바(Java)

1) 난이도 : D3

 

2) 문제번호 : 3307번

 

3) 문제 출처

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr

SW Expert Academy

 

2. 문제

주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 프로그램을 작성하시오.

수열 { A1, A2, ... , AN }의 최장 증가 부분 수열 B는 다음과 같이 정의된다.

{ B1, B2, ... , BK }에서 0≤K≤N, B1 ≤ B2 ≤ ... ≤ BK이고,

AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.

예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.

 

3. 제약사항

- 

 

4. 입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 수열의 길이 N(1≤N≤1,000)이 주어진다. 

둘째 줄에는 수열의 원소 N개가 공백을 사이에 두고 순서대로 주어진다.

각 수열의 원소는 1 이상 231-1 이하의 자연수이다.

 

5. 출력

각 테스트 케이스마다 ‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 증가 부분 수열의 길이를 출력한다.

 

6. 풀이

- 간단한 최장 증가 부분 수열의 기본 문제이다.

- 최장 증가 부분 수열의 개념을 알면 된다.

7. 소스 코드

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); //테스트케이스 개수
		
		for(int tc=1;tc<=T;tc++) {
			int N = sc.nextInt(); // 수열의 길이
			
			//첫 번째 행에는 수열 값
			//두 번째 행에는 LIS
			int[][] DP = new int[2][N];
			
			int max = 0;
			
			//수열 값 입력
			for(int i=0;i<N;i++) DP[0][i] = sc.nextInt();
			
			for(int i=0;i<N;i++) {
				DP[1][i] = 1;
				
				for(int j=0;j<i;j++) {
					if(DP[0][j]<DP[0][i] && DP[1][i] < DP[1][j]+1) {
						DP[1][i] = DP[1][j] + 1;
					}
				}
				if(max<DP[1][i]) max = DP[1][i];
			}
			System.out.printf("#%d %d\n",tc, max);
		}
		
		
	}
}

---