BOJ(C++) / 백준 11053 : 가장 긴 증가하는 부분 수열

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

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

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

 

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

코드

//백준 가장 긴 증가하는 부분 수열 11053
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	int N;
	cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		int max_num = 0; 
		for (int j = 0; j < i; j++) {
			if (v[i] > v[j]) // 작은 수 
				max_num = max(max_num, dp[j]); // 작은 수 중 길이가 가장 긴 것
		}
		dp[i] = max_num + 1; //가장 긴 것을 골라 +1(자기 자신 추가)
		answer = max(answer, dp[i]); //가장 긴 길이
	}

	cout << answer << "\n";

	return 0;
}

 

설명

• DP(dynamic programming)로 문제를 풀 수 있다. 
• 인덱스 i 위치에서 그 전 위치까지 중 작은 수들 중 dp배열의 값이 가장 큰 값을 고른다.
• 가장 큰 값을 골라 인덱스 i의 dp의 값을 +1 하여 업데이트시켜준다.
• dp의 값 중 가장 큰 값을 골라 출력할 수 있다. 

고찰

걸린 시간 : 20분

DP문제 치고는 어렵지 않게 문제를 풀 수 있었다. 

DP라는 것을 알고 문제를 풀 때는 괜찮은데 모르고 문제를 풀 때는 조금 어려운 거 같다. 알고리즘을 생각을 하고 문제를 풀어야 할 거 같다.

 

난이도

Silver 2