[BOJ/백준] 11053 가장 긴 증가하는 부분 수열

● [문제번호 11053] 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

: Longest Increasing Subsequence

 

● 풀이 과정

: 시간복잡도가 O( N^2 ) 인데 더 줄일 수 없는 방법을 고민하다가

일단 채점했는데 통과되었다.

 

: DP의 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ {맨 앞부터 index에 있는 숫자까지}의 {가장 긴 증가하는 수열의 길이}

 

2. 점화식 찾기

→ dp[index] = max( dp[index], dp[circuit] + 1 )

 

3. 초기값 정하기

→ 모든 dp의 값은 1부터 시작

● 주의 할 것

: dp배열의 값이 업데이트 될 때

기존 값과 앞 배열에서 1을 더하여 가져오는 값 중 큰 값을 저장해야한다.

 

● 참고 할 것

: 풀이과정

https://bitwise.tistory.com/215

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// A : 입력 받는 배열
// dp : 가장 긴 증가하는 수열의 길이를 저장하는 배열
vector<int> A, dp;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    A.assign(N + 1, 0);
    dp.assign(N + 1, 1);
    
    // 입력
    for(int n = 1; n <= N; n++)
        cin >> A[n];
    
    // a : 기준 index
    for(int a = 1; a <= N; a++)
    {
        // b : 비교 index
        for(int b = 1; b < a; b++)
        {
            // 기준보다 작은 숫자인 경우
            if(A[b] < A[a])
                dp[a] = max(dp[a], dp[b] + 1);
        }
    }
    
    cout << *max_element(dp.begin(), dp.end());
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212