Normal_11053_가장 큰 증가하는 부분 수열

문제 링크(Click) : https://www.acmicpc.net/problem/11053

1. 문제 접근

---

1) 문제가 반복되는지? 즉, 재귀/DP 문제인지 파악합니다.

  먼저, 문제에서 주어진 예시를 통해서 문제의 요구사항을 파악해 보겠습니다. 

 " 수열 A = {10, 20, 10, 30, 20, 50}에서 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성해라 "

  문제에서 직접적으로 명시된 조건은 따로 없지만, 가장 길면서 증가하는 부분 수열을 구하는 것이 저희 목표입니다.

  저는 이러한 DP 문제에 접근할 때, 오른쪽 끝에서부터 생각을 하는 습관이 도움이 된다고 생각합니다. 이렇게 오른쪽 끝에서부터 생각하기 위해서는 문제의 답에는 영향을 주지 않는 하에서, 문제의 조건을 살짝 변형시켜줘야 합니다. 

  " 10 -> 20 - > 30 " == " 10 <- 20 <- 30 "

  즉, 오른쪽에서 왼쪽으로 가장 긴 감소하는 부분 수열의 길이를 구하는 것으로 생각을 전환한다면, 문제의 답에는 영향을 주지 않습니다. 이를 통해, 현재 선택한 수(n)를 기준으로, 다음(n-1)부터 왼쪽 끝(1)까지 수 중 작은 수를 골라야 한다는 것을 확인할 수 있습니다. 위의 경우는 30을 처음 선택시(4), 그보다 작은 10(3)과 20(2), 그리고 10(1) 중 하나를 선택할 수 있고, 이들 중 가장 길이의 값이 가장 큰 값을 선택해 주면 된다는 것을 알 수 있습니다.

  하지만 지금같이 진행했던 것은 처음의 수가 30을 선택했을 때입니다. 하지만 굳이 처음의 수부터 진행해야 답이라는 확증이 없기 때문에 각각의 index에서 시작하는 경우를 모두 따져봐야합니다.

 

 2) 종료 조건을 파악합니다.

  위 그림은 총 길이가 4인 증가하는 부분 수열입니다. index가 1을 마지막으로 길이를 계산하는 것은 끝이나야하기 때문에, 그보다 작은 0을 마지막으로 0을 반환해줍니다. 따라서 n이 0일때, 재귀함수의 종료 조건이라는 것을 알 수 있습니다. 

 if(n == 0) return 0;

 3) 반복 패턴을 코드화 합니다.

  1) 에서 이야기 했던 것처럼, 현재 선택한 수(n)를 기준으로, 다음(n-1)부터 왼쪽 끝(1)까지 수 중 작은 수를 골라야 한다는 것을 확인할 수 있습니다. 따라서 현재수(index n)와 나머지수들(index n-1 ~ 1)을 비교하여, 나머지수들이 현재 수보다 작을때, 만들어질 수 있는 길이 중 최대값을 선택하도록 비교를 진행해야합니다. 따라서 다음과 같이 코드화 할 수 있습니다.

for(int i = n-1; i > 0; i--) {

if(num[n] > num[i])

d[n] = Math.max(d[n], dp(i)+1);

}

2. 코드 종합

---

 위에서 정리된 코드들을 아래의 순서로 정리하면 완성할 수 있습니다.

 1) 종료 조건

 2) Memoization

 3) 반복 패턴

 4) return d[n];

import java.util.Scanner;

public class p11053 {

static int[] d;

static int[] num;

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

d = new int[n+1];

num = new int[n+1];

for(int i = 1; i <= n; i++) {

num[i] = scan.nextInt();

}

int output = 0;

for(int i = n; i >= 1; i--) {

// dp(i)에 1을 더해준 이유는 dp(i) 자체가 해당 index의 i를 포함하고 시작한다는 의미이기 때문입니다.

output = Math.max(output, dp(i)+1);

}

System.out.println(output);

}

public static int dp(int n) {

if(n == 0)

return 0;

if(d[n] > 0)

return d[n];

for(int i = n-1; i > 0; i--) {

if(num[n] > num[i])

d[n] = Math.max(d[n], dp(i)+1);

}

return d[n];

}

}