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

문제

주어진 두 수열의 최장 증가 부분 수열(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가 된다.

입력

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

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

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

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

출력

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

예제 입력

2
5
1 3 2 5 4 
6
4 2 3 1 5 6

예제 출력

#1 3
#2 4

코드

package live11._01_최장_증가_부분_수열;

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

public class Solution {
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/live11/_01_최장_증가_부분_수열/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

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

		for (int tc = 1; tc <= T; tc++) {
			int numArrLength = Integer.parseInt(br.readLine());
			int[] numArr = new int[numArrLength];
			int[] dp = new int[numArrLength];
			int answer = 0;

			// 수열 받기
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < numArrLength; i++) {
				numArr[i] = Integer.parseInt(st.nextToken());
			}

			Arrays.fill(dp, 1);

			for (int i = 0; i < numArrLength; i++) {
				for (int j = 0; j < i; j++) {
					if (numArr[j] < numArr[i]) {
						dp[i] = Math.max(dp[i], dp[j] + 1);
					}
				}
				answer = Math.max(answer, dp[i]);
			}

			bw.write("#" + tc + " " + answer + "\n");
		}

		br.close();
		bw.close();
	}
}

풀이

💡 DP의 의미와 초기값

int[] dp = new int[numArrLength];
Arrays.fill(dp, 1);

• dp는 numArr의 인덱스와 1대1 매칭입니다.
• dp[i]는 i번째 숫자를 마지막으로 하는 최장 길이입니다.
  • 예시 입력값을 예로 들면, 1 3 2 5 4에서 3은 1번째 숫자이며, 이 숫자를 마지막으로 하는 최장 길이는 1과 3이 되므로 2가 됩니다.
• 초기값은 모든 숫자들이 한 번씩은 들어갈 수 있기 때문에 1로 초기화합니다.
• 주의점은 3의 앞에 있는 숫자와 비교하여 최장 길이를 계산해야합니다.
  • 예를 들면, 5앞에 있는 숫자는 1 3 2가 됩니다.

💡 점화식

for (int i = 0; i < numArrLength; i++) {
	for (int j = 0; j < i; j++) {
		if (numArr[j] < numArr[i]) {
			dp[i] = Math.max(dp[i], dp[j] + 1);
		}
	}
	answer = Math.max(answer, dp[i]);
}

1. for문은 현재 위치의 값과 이전 모두의 값을 비교하게됩니다.
   1-1) 바깥쪽 for문은 현재값입니다.
   1-2) 안쪽 for문은 이전값들입니다.
2. if문은 현재 위치의 값과 이전 값들을 비교하기 위한 조건입니다.
   현재 위치의 값보다 나중인 값은 비교하면 내 앞에 있는 숫자들 중에서 나보다 작은 숫자를 봐야한다는 조건을 못 지키게 됩니다.
3. dp[i] = 현재 위치의 최장 길이
   • dp[j] + 1로 현재 위치의 값보다 작은 값이 있다는 것을 저장합니다.
   • i = 1일 때
     • 1과 3을 비교하게 되며, 3이 더 크기 때문에
     • dp[j] + 1로 dp = { 1, 2, 1, 1, 1 } 이 됩니다.
   • i = 2일 때
     • 1과 2, 3과 2 총 2번을 비교하게 됩니다.
     • 1과 비교했을 때 dp[j] + 1을 하게되지만,
     • 3과 비교했을 때 2가 더 작으니 조건을 벗어나게 됩니다.
     • 따라서 dp = { 1, 2, 2, 1, 1 } 이 됩니다.
   • i = 3일 때
     • 1과 5, 3과 5, 2와 5 총 3번을 비교하게 됩니다.
     • 1과 비교했을 때 dp[j] + 1
     • 3과 비교했을 때 dp[j] + 1
     • 2와 비교했을 때 dp[j] + 1
     • 따라서 dp = { 1, 2, 2, 3, 1 } 이 됩니다.
   • i = 4일 때
     • 위의 규칙에 따라 총 4번을 비교하게 됩니다.
     • 5와 4를 비교했을 때만 조건을 벗어나게 되므로
     • dp = { 1, 2, 2, 3, 3 } 이 됩니다.
4. dp의 가장 큰 값을 answer의 담아서 출력하면 최장 길이 문제 해결입니다!