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

👀 문제 설명

문제

수열 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

6

10 20 10 30 20 50

 

예제 출력 1

4

 

✍🏻풀이

부분 수열의 길이를 담는 배열 dp를 선언한다. (초기화는 1)

dp[i]에는 i까지의 가능한 부분 수열 중, 가장 긴 값을 담고 있다.

 

dp[i]를 구하는 방법은,

인덱스 0부터 i - 1 까지의 a[j] 값들 중, a[i]보다 작은 값일 때, dp[j]의 max값을 구하고, 거기에 +1을 더해준다. (i 위치 추가)

 

//

나는 처음에 dp 배열의 원소를 0으로 초기화했고, dp[0], dp[1]만 먼저 구해서 넣어줬다.

인덱스 2부터 N-1까지 dp값을 구할 때, maxDp라는 변수를 갖고 dp[i]값을 구했다.

maxDp를 0으로 초기화하고, maxDp = max(maxDp, dp[j]) 를 통해 a[j]가 a[i]보다 작은 인덱스 j의 dp 값 중에서 가장 큰 dp값을 maxDp에 넣었고, dp[i] = maxDp + 1을 해줬다.

그런데 내가 생각한 테스트케이스와 백준에서의 테스트 케이스가 모두 맞는 답으로 나왔는데도 불구하고, 자꾸 틀렸다고 떴다..

그래서 maxDp를 쓰지 않고, dp배열을 1로 초기화한 후, dp배열만 사용해서 풀었더니 정답이 되었다 (근데 아무리 봐도 차이를 모르겠음..ㅠ)

=> 오류 발견! 수열 A의 크기가 1일 때 답이 -1로 리턴된다!

아래 처음 짠 코드에서 보면, for문에는 i가 2보다 크거나 같을 때만 들어가므로, 이 부분이 문제였다.

 

코드

처음 짠 코드 (틀린 답이라고 나온다)

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int N;
int a[1000];
int dp[1000];
int main() {
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    // dp
    // dp[i]에는 i까지의 증가하는 부분 수열이 가장 긴 값을 담고 있다.
    // 처음부터 i - 1까지의 a[n]중, a[i]보다 작은 값들 중, dp의 max값에서 +1(현재 값 추가) 하면 될듯?
    dp[0] = 1;
    int ans = -1;
    
    if (a[0] < a[1]) {
        dp[1] = 2;
    }
    else {
        dp[1] = 1;
    }

    for (int i = 2; i < N; i++) {
        int maxDp = 0;

        for (int j = 0; j <= i - 1; j++) {
            if (a[j] < a[i]) {
                maxDp = max(maxDp, dp[j]);
            }
        }
        
        dp[i] = maxDp + 1;
        ans = max(ans, dp[i]);
    }
    
    cout << ans << endl;
    
    return 0;
}

 

고친 답(정답)

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int N;
int a[1000];
int dp[1000];

int main() {
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    // dp
    // dp[i]에는 i까지의 증가하는 부분 수열이 가장 긴 값을 담고 있다.
    // 처음부터 i - 1까지의 a[n]중, a[i]보다 작은 값들 중, dp의 max값에서 +1(현재 값 추가) 하면 될듯?
    dp[0] = 1;
    int ans = -1;
    
    for (int i = 0; i < N; i++) {
        int maxDp = 0;
        
        for (int j = 0; j <= i - 1; j++) {
            if (a[j] < a[i]) {
                maxDp = max(maxDp, dp[j]);
            }
        }
        
        dp[i] = maxDp + 1;
        ans = max(ans, dp[i]);
    }
    
    cout << ans << endl;
    
    return 0;
}

 

정답

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int N;
int a[1000];
int dp[1000];

int main() {
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    fill_n(dp, 1000, 1); // 배열 원소 1로 초기화
    
    // dp
    // dp[i]에는 i까지의 증가하는 부분 수열이 가장 긴 값을 담고 있다.
    // 처음부터 i - 1까지의 a[n]중, a[i]보다 작은 값들 중, dp의 max값에서 +1(현재 값 추가) 하면 될듯?
    int ans = 1;
    
    if (a[0] < a[1]) {
        dp[1] += 1;
    }
    
    for (int i = 2; i < N; i++) {
        for (int j = 0; j <= i - 1; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        
        ans = max(ans, dp[i]);
    }
    
    cout << ans << endl;
    
    return 0;
}