[백준] G4 14002번 가장 긴 증가하는 부분 수열 4

문제 출처 - Baekjoon Online Judge

문제는 여기

14002번: 가장 긴 증가하는 부분 수열 4

[문제] 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

[입력]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

[출력]

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

---

[풀이]

1. 입력을 받아 map 배열을 채워준다.

2. 결과를 출력하기 위한 result 변수를 선언해준다.

3. 시작은 무조건 1이므로 dp배열을 1로 채워준다.

4. 현재 값 이전까지 값들을 비교해서 더 큰 값을 찾아준다.

5. 더 큰 값이 나오면 해당 번째의 dp 배열의 값 + 1과 현재 dp 배열의 값을 비교하여 더 큰 것으로 갱신해준다.

6. result에 최대값을 갱신해준다.

7. 모든 배열을 탐색하고 나면 StringBuilder에 result를 담아준다.

8. 해당하는 원소값을 담아둘 스택을 선언해준다.

9. 최장 길이와 dp의 값이 같은 경우 스택에 담아주고 이를 배열의 역순으로 반복한다.

10. 스택에 담긴 값들을 빼서 7. 에서 만든 StringBuilder에 담아준다.

11. 결과를 출력한다.

[접근]

1. 가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열을 구하듯이 구하면 되겠다고 생각하였다.

2. 길이에 해당하는 원소를 어떻게 찾을 까 생각했는데, 최대 길이를 구하고 나면 해당 길이와 dp 배열의 값을 비교해 값을 찾아나가면 되겠다고 생각하였다.

[코드]

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int map[] = new int[n + 1];
		int dp[] = new int[n + 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		// 값 채워주기
		for (int i = 1; i <= n; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = 1;
		// 최장길이, 최단길이를 구할 때 처럼 문제를 풀면 된다.
		for (int i = 1; i <= n; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (map[i] > map[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
					result = Math.max(dp[i], result);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		// 최고 길이 저장
		sb.append(result + "\n");
		
		// 스택을 사용해 최장 길이의 원소들을 담아줄 것
		Stack<Integer> s = new Stack<>();
		// 역순으로 탐색
		for(int i = n; i > 0; i--) {
			// 최장 길이와 해당 dp 값이 같다면
			if(dp[i] == result) {
				// 해당하는 원소의 값을 스택에 담아주기
				s.push(map[i]);
				// 하나의 원소를 담아줬으므로 길이 -1
				result--;
			}
		}
		
		// 스택에 있는 값들을 다 스트링빌더에 담아주기
		while(!s.isEmpty()) {
			sb.append(s.pop() + " ");
		}
		
		System.out.println(sb.toString());
	}
}

---

비슷한 문제로 아래의 문제를 풀었었다.

[백준] S2 11722번 가장 긴 감소하는 부분 수열 (JAVA)