문제

BOJ 14002: 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002

풀이

조건

• 가장 긴 증가하는 부분 수열을 구한다.
• 수열의 크기 N의 범위: (1 ≤ N ≤ 1,000)
• 수열을 이루고 있는 값의 범위 (1 ≤ Ai ≤ 1,000)

풀이 순서

• 각 위치의 값마다 이전의 값들을 탐색한다.
  • 자신의 값보다 작은 값을 찾으면 해당 위치에 있는 값이 포함된 부분 수열의 길이를 확인한다.
  • 확인한 길이 중 가장 긴 값을 구해 현재 값에 저장한다.
    • 이 때, 그 위치를 저장한다.
• 가장 긴 길이를 구하는 것은 쉽지만 부분 수열의 값들을 출력하는 점이 까다로웠을 것이다.
  이는 각 위치에서 이전의 값을 찾아갈 때 그 위치를 저장해주면 된다.

예제 1을 예로 들면

인덱스	0	1	2	3	4	5	6
배열	-1	10	20	10	30	20	50
수열의 길이	0	1	2	1	3	2	4
이전 값의 위치	-1	0	1	0	2	3	4

이런 식으로 저장이 된다.

증가하는 부분 수열 중 가장 긴 값은 6번 인덱스가 포함된 4이다.
따라서 6번 인덱스의 이전 값의 위치인 4번 인덱스로 넘어가면 2번 인덱스가 저장되어 있고
2번 인덱스의 이전 값의 위치는 1로 저장되어 있고
1번 인덱스에 저장되어 있는 이전 값인 0으로 넘어가면 -1이 나온다.

위의 순서대로 해당 위치에 있는 값을 출력하면 50 -> 30 -> 20 -> 10 이 된다.

이를 순서대로 출력하면 10 -> 20 -> 30 -> 50이 된다.

코드

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

public class Main {

    static int N; // 수열의 길이
    static int[] arr; // 입력받은 수열의 값을 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1]; // 입력받은 수열의 값을 저장할 배열

		// 수열의 값 입력
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answerCnt = -1; // 가장 긴 증가하는 부분 수열의 길이
        int answerLastPos = -1; // 가장 긴 증가하는 부분 수열의 마지막 값의 위치 
		
        // 증가하는 부분 수열의 정보를 저장할 배열
        Node[] nodes = new Node[N + 1];
        for(int i = 0; i <= N; i++) {
            nodes[i] = new Node(-1, 0);
        }
        // 0번째 값은 이전 위치가 -1, 길이가 0
        nodes[0] = new Node(-1, 0);
        
        // 1부터 N 까지의 값을 확인
        for(int i = 1; i <= N; i++) {
            int now = arr[i]; // 현재 값
            int before = nodes[i].before; // 바로 이전 값의 위치
            
            // 바로 전 위치부터 0번째 위치까지 확인
            for(int j = i - 1; j >= 0; j--) {
                int temp = arr[j];
                int mCnt = nodes[i].cnt;
				
                // 현재 값보다 이전의 값이 더 작다면
                // 현재 증가하고 있다는 뜻
                if(temp < now) {
					// 증가하는 부분 수열의 길이 중 가장 긴 값으로 갱신
                    if(mCnt < nodes[j].cnt + 1) {
                        mCnt = nodes[j].cnt + 1;
                        // 바로 이전으로 찾아갈 위치 저장
                        before = j;
                    }
                }
                // 바로 이전의 위치, 부분 수열의 길이로 객체 저장
                nodes[i] = new Node(before, mCnt);
				
                // 더 긴 부분 수열의 길이를 찾았다면
                // 정답에 사용할 값 갱신
                if(nodes[i].cnt >= answerCnt) {
                    answerCnt = nodes[i].cnt;
                    answerLastPos = i;
                }
            }
        }
		
        // 저장해놓은 before 위치들을 찾으며 값 저장
        StringBuilder sb = new StringBuilder();
        int nextPos = answerLastPos;
        while (nextPos > 0) {
            sb.insert(0, arr[nextPos] + " ");
            nextPos = nodes[nextPos].before;
        }
		// 가장 긴 부분 수열의 길이
        System.out.println(answerCnt);
        // 부분 수열 출력
        System.out.println(sb);

    }
	
    static class Node {
        int before; // 이전 값의 위치
        int cnt; // 현재 값이 증가하는 부분 수열 중 몇 번째 값인지

        public Node(int before, int cnt) {
            this.before = before;
            this.cnt = cnt;
        }
    }


}

정리

• 증가하는 가장 긴 부분 수열의 길이를 구하는 것은 쉬웠다.
• 해당 수열의 값을 찾는 부분도 이전의 위치를 저장하는 방식으로 풀이하는 다른 문제를 푼 적이 있어 쉽게 떠올릴 수 있었다.