[알고리즘]백준 11722_가장 긴 감소하는 부분 수열

백준_11722

• 인덱스 간격이 1인 값부터 비교해서 앞의 값 > 뒤의 값이면 cnt[앞 인덱스] += cnt[뒤 인덱스]로 누적하고,
  그 다음엔 간격을 2, 3… n-1까지 늘려가며
  가장 크게 누적된 값을 답으로 리턴
• 하지만 중복해서 더해주는 문제 발생
  • ex) lst 3,2,1 에서 cnt_lst 1,1,1 로 초기화 후 재귀끝내면 4,2,1이 되버림. 의도는 3,2,1. 출력은 expected = 3, output=4
  • 1이 이미 카운트됐는데 중복 카운트.

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

public class Main {

    // 재귀로 갱신
    static int count(int[] l, int[] c, int n, int cpN, int max_n) {
        if (cpN == n) {
            return max_n;
        }

	// 뒤에서 부터. 
        for (int i = n - 1; i >= cpN; i--) {
            if (l[i - cpN] > l[i]) {
                c[i - cpN] += c[i];
            }
            if (max_n < c[i - cpN]) {
                max_n = c[i - cpN];
            }
        }

        return count(l, c, n, cpN + 1, max_n);
    }

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

        int N = Integer.parseInt(br.readLine());
        int[] lst = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            lst[i] = Integer.parseInt(st.nextToken());
        }

        int[] cnt_lst = new int[N];
        // 기본적으로 카운트 1씩
        Arrays.fill(cnt_lst, 1);

        int result = count(lst, cnt_lst, N, 1, 1);
        System.out.println(result);
    }
}

• 다시 풀기
• dp[i] = i에서 끝나는 가장 긴 감소 부분 수열의 길이
• j < i 이고 arr[j] > arr[i] 라면 dp[i] = max(dp[i], dp[j] + 1)
• 가능한 이전 원소들 중에서 가장 긴 것 하나만 이어붙임

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

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[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

		// dp 1로 초기화. 일단 하나 카운트라는 뜻
        int[] dp = new int[N];
        Arrays.fill(dp, 1); 

        int answer = 1;

        for (int i = 0; i < N; i++) {
        	// j < i, arr[j] > arr[i]
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) {               
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 최대값 갱신
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);
    }
}

/*

N = 6
arr = [10, 30, 10, 20, 20, 10]

arr = [10, 30, 10, 20, 20, 10]
dp  = [ 1,  1,  1,  1,  1,  1]  // 모두 자기 자신만 포함
answer = 1

i=0
dp = [1, 1, 1, 1, 1, 1]
answer = 1

i=1
dp = [1, 1, 1, 1, 1, 1]
answer = 1

i=2
dp = [1, 1, 2, 1, 1, 1]
answer = 2

i=3
dp = [1, 1, 2, 2, 1, 1]
answer = 2

i=4
dp = [1, 1, 2, 2, 2, 1]
answer = 2

i=5
dp = [1, 1, 2, 2, 2, 3]
answer = 3

결과 = 3

*/