가장_긴_증가하는_부분수열[BOJ_11053]

오늘은 BOJ 11053 문제인 가장 긴 증가하는 부분수열을 구하는 문제를 풀어보겠습니다.

마찬가지로 DP 방식대로 풀 것 입니다. 

DP 관련 문제를 많이 풀다보면 DP가 적응되어서 상당히 유형을 확인하는 눈이 넓어지는 것 같습니다.

DP(다이나믹프로그래밍)에서 가장 중요한 것은 점화식입니다.

Top-Bottom 이던 Bottom-Up 이던 결국 N번째 식에서의 점화식이 중요합니다.

그리고 이를 메모하는 배열을 만들어줍니다. 

d 또는 dp로 배열 이름을 설정해주고 풀게 되면 됩니다.

DP는 문제를 많이 풀고 유형을 익혀야 합니다. 

따라서 설명을 줄이고 문제에서 유형을 체크해보겠습니다. 

N이 현재 1000 이하 입니다.

따라서 자료형을 int로해서 진행해도 됩니다.

또한 이러한 문제는 DP 방식으로 풀 경우, 먼저 N번째 일 경우는 어떻게 될 지 생각을 해야 합니다.

점화식 : D[n]은 길이가 N인 배열에서 가장 긴 증가하는 부분 수열의 길이

N-1 번째는 길이가 N-1인 배열에서 가장 긴 증가하는 부분 수열의 길이 

N-2 번째는 길이가 N-2인 배열에서 가장 긴 증가하는 부분 수열의 길이

.

.

.

결국 이렇게 하나씩 차이난다고 생각한다면, D[n]은 다음과 같이 정의할 수 있습니다.

D[n]은 D[n-1] + 1 ; 

이는 길이이기 때문에 가능한 점화식입니다. 

만약에 값에 관한 것이라면 +1 이 아니라 n번째의 배열의 값이 들어가겠죠? (가령 a[n] 과 같은..)

그리고 만약 저러한 상황에서 케이스가 여러개로 나뉘어 진다면, 2차 배열의 DP방식으로 

케이스 별로 값을 더해줘서 구하는 경우도 있습니다.

예 : ) D[n] = D[n-1] + a[n][0] ;  //   D[n] = D[n-1] + a[n][1] // ..... 

(케이스로 나뉘어서 DP를 푸는 방법은 다음 포스팅에 적겠습니다.)

따라서 예제 입력을 확인하면 다음과 같습니다. 

우선 i , j 변수를 사용해서 푼다고 가정하고, j가 i보다 한 칸 작은 값 (앞서 설명한 n-1 과 n 관계로 생각)

으로 가정해서 풀겠습니다.

※ 조건은 다음과 같습니다.

i > j

A[i] > A[j]

--> 인덱스는 당연히 i가 더 커야하고 증가하는 부분 수열이기 때문에 A[i] 또한 A[j] 보다 커야합니다.

초기에 부분수열의 길이는 1입니다.

원소가 하나만 있더라도 길이는 1이기 때문입니다.

인덱스는 i가 더크고 A[i] 보다 작은 값들 중 최대의 값의 D[j] (0<= j <= i-1) 값을 가져와서

1을 더해주면 D[i]가 나오게 됩니다. 

따라서 코드는 다음과 같습니다.

---

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

d[i] = 1;

for (int j = 0; j < i; j++) {

// a[i] > a[j] 는 기본 조건

// d[i] = Math.max(d[j]) + 1 --> 이 말인 즉, d[i]를 계속 돌면서 d[j] + 1과 비교해서

// d[j] + 1이 더 크면 d[i]에 등록됨 .

// 이 과정이 반복되면 결국 가장 큰 값이 d[i]에 들어갈 것

if (a[i] > a[j] && d[i] < d[j] + 1) {

d[i] = d[j] + 1;

}

}

}

int ans = 0;

for (int i = 0; i < n; i++)

ans = Math.max(d[i], ans);

---

이렇게 코드를 정리해주면 앞서 설정한 전제조건도 만족하면서 최대 값을 i와 j로 계속해서 반복문을 돌면서

확인할 수 있습니다.

그렇게 해서 나온 최대값은 d[i]에 넣어주고, 넣어진 d[i]에서 최대 값을 다시

체크해서 ans라는 변수에 넣어줍니다.

이를 출력하면 정답이 출력될 것 입니다.

전체 코드는 다음과 같습니다.

---

import java.util.Scanner;

public class 가장_긴_증가하는_부분수열 {

private static Scanner scanner;

private static int[] d;

private static int[] a;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int n = scanner.nextInt();

d = new int[n + 1]; // a[0] ~ a[n] 까지의 값 중 가장 긴 부분수열의 값

a = new int[n + 1]; // a[0] ~ a[n] 값이 있음

for (int i = 0; i < n; i++)

a[i] = scanner.nextInt();

/*

* 조건 1. 증가하는 수열이어야 한다. --> 증가하지 않으면 우선 1부터 시작 (원래 1부터 시작하지만..) 2. 인덱스 j는 i보다 한

* 칸 작은 수라고 가정한다면, j<i이며 A[j]<A[i] 이어야 한다. 3. 2번 조건을 만족하면서 가장 큰 값을 구해서 D[i]에

* 넣어주면서 +1을 해주면 된다. (이유는 j가 i보다 인덱스상 하나가 적은 값이기 때문이다.

*/

// d[i] 값은 모두 우선 1을 가지고 들어갑니다.

// 여기서 큰 값을 바꿔주는 형식으로 진행

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

d[i] = 1;

for (int j = 0; j < i; j++) {

// a[i] > a[j] 는 기본 조건

// d[i] = Math.max(d[j]) + 1 --> 이 말인 즉, d[i]를 계속 돌면서 d[j] + 1과 비교해서

// d[j] + 1이 더 크면 d[i]에 등록됨 .

// 이 과정이 반복되면 결국 가장 큰 값이 d[i]에 들어갈 것

if (a[i] > a[j] && d[i] < d[j] + 1) {

d[i] = d[j] + 1;

}

}

}

int ans = 0;

for (int i = 0; i < n; i++)

ans = Math.max(d[i], ans);

System.out.println(ans);

}

}

---

감사합니다 =)