[boj] 가장 긴 증가하는 부분수열_11053 (완전탐색, DP)

N = int(input())

array = list(map(int, input().split()))
dp = [1 for i in range(N)]
temp_list = list()

for i in range(N):
    for j in range(i):
        if array[i] > array[j]:
            temp_list.append(dp[j]+1)
            temp = max(temp_list)
            dp[i] = temp
    temp_list.clear()

print(max(dp))

for i in range(N):
    for j in range(i):
        if array[i] > array[j] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1

print(max(dp))

두 코드 모두 맞는 코드이고 동일하게 아래의 알고리즘으로 풀었다. 그런데 두 번째 코드는 내가 다시보고 이해안가서 첫 번째로 다시풀었다...

 

 

주어진 수열에서 가장 긴 부분 증가 수열을 만드는 문제였다.

 

DP를 활용한 문제인데 생소한 개념이라 접근이 쉽지 않았다.

다이나믹 프로그래밍은 보통 DP 리스트(배열)을 통해 이전에 계산한 값을 활용하여 다음 계산의 불필요한 계산을 줄이는 방식을 사용한다.

 

이 문제에서는 현재의 값과 이전의 값을 비교하여 더 작은 값이 있다면, 증가하는 수열이 만들어 지는 것이라고 생각하여 문제를 해결해 나간다.

 

입력 받은 값을 Array, Array에 해당하는 값에서 만들어지는 부분 수열의 수를 dp라 하자.

처음에는 자기자신만을 포함하므로 dp값은 모두 1이다.

 

이제 반복문을 통해 입력 값을 순차적으로 탐색한다.

10의 경우 자기 자신보다 작은 이전의 값이 없으므로 부분 수열의 길이는 1이다.

 

 

다음으로 20을 보자.

20의 경우 앞에 10이 있으므로 만들어지는 부분수열의 길이는 10, 20 총 2이다.

 

 

그 다음 10을 보자.

처음과 마찬가지로 10보다 작은 수가 없으므로 10으로 만들어지는 부분수열의 길이는 자기 자신인 1이다.

 

다음 입력인 30을 보자.

30의 경우에는 10, 20이 앞에 있으므로 만들어지는 증가하는 부분수열의 길이는 10, 20, 30으로 총 3이다.

 

그런데 이때, 부분수열의 길이 3은 직접 10과 20을 세는 것이 아닌, 20의 부분 수열 길이 2를 이용한다는 것이 중요한 포인트이다.

왜냐하면, 20의 부분 수열 길이는 이미 앞에 있는 10을 포함한 길이이기 때문이다.

 

 

다음 입력값인 50도 같은 방법으로 30의 dp값을 이용하여 풀어주면 최종 길이인 4를 구할 수 있다.

 

 

+) 처음에는 나올 수 있는 모든 경우의 수를 구하고 이를 다 따지는 완전탐색을 통해 문제를 풀었다.

대부분의 반례를 모두 통과하는 결과를 얻었지만 완전탐색이라 그런지 시간초과로 통과하지 못했다 ㅠㅠ

 

# 완전탐색을 이용한 풀이
N = int(input())

array = list(map(int, input().split()))

for i in range(N):
    if i != N-1:
        for j in range(i+1, N):
            temp_list.append(array[i])
            for k in range(j, N):
                if array[k] > temp_list[-1]:
                    temp_list.append(array[k])
            temp = len(temp_list)
            if count <= temp:
                count = temp
            temp_list.clear()
    else:
        temp_list.append(array[i])
        temp = len(temp_list)
        if count <= temp:
            count = temp
        temp_list.clear()
print(count)

 

+) 이전 풀이 중 c++을 이용한 풀이가 있어 첨부한다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> Data;
vector<int> dp;
vector<int> temp_dp;

int getMax(vector<int> temp) {
	int max = temp[0];
	for (int i = 0; i < temp.size(); i++) {
		if (temp[i] > max) {
			max = temp[i];
		}
		else {
			continue;
		}
	}
	return max;
}

int main() {
	int N;
	int M;

	cin >> N;

	dp.push_back(1);

	for (int i = 0; i < N; i++) {
		cin >> M;
		Data.push_back(M);
	}
	for (int i = 1; i < Data.size(); i++) {
		for (int j = 0; j <= i - 1; j++) {
			if (Data[i] > Data[j]) {
				temp_dp.push_back(dp[j] + 1);
			}
			else if (Data[i] == Data[j]) {
				temp_dp.push_back(dp[j]);
			}
			else {
				temp_dp.push_back(1);
			}
		}
		int temp = getMax(temp_dp);
		dp.push_back(temp);
		temp_dp.clear();
	}
	int result = getMax(dp);
	cout << result;
	return 0;
}