11053 가장 긴 증가하는 부분 수열 ★

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 1000
// 11053
 
int max(int a, int b) {return a > b ? a : b;}
int max(int a, int b, int c){
	return max(a, b) < c ? c : max(a, b);
}
 
int main(){
	int n;
	
	cin >> n;
	cin.ignore();
	
	vector<int> vec(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> vec[i];
	}
	
	vector<int> mem(n + 1, 1); // 해당 숫자에서의 최대 배열 길이를 저장 
	for(int i = 2; i <= n; i++){
		int maxMem = -1, maxIdx = 0;
		for(int j = 1; j < i; j++){
			if(vec[j] >= vec[i]) continue;
			if(maxMem < mem[j]) {maxMem = mem[j]; maxIdx = j;}
		}
		if(maxMem != -1) mem[i] = mem[maxIdx] + 1;
	}
	
	int res = -1;
	for(int i = 1; i <= n; i++){
		if(res < mem[i]) res = mem[i];
	}
	
	cout << res << endl;
 
}

 

해설

어떠한 방식으로 문제를 바라보느냐가 참 중요한 것 같습니다. 감이 잡히지 않던 문제도 다른 사람의 접근 과정을 보면 바로 생각이 떠으릅니다. 이 문제에서도 마찬가지 였는데, 동적 계획법 (dp) 로 문제에 접근할 때는 참 다양한 생각이 듭니다.

메모이제이션. 이전 단계까지의 결과를 저장해두어서 알고리즘의 효율을 높이는 방식입니다. 이 문제에서도 메모이제이션이 사용되었는데 메모이제이션을 어떻게 적용하느냐가 관건이었습니다.

Iterate  하면서, 해당 수가 마지막으로 끝날 경우의 최대 배열의 수 를 메모이제이션 해두고 푸는 접근이 가장 타당했습니다.

그렇다면 어떻게 이러한 접근법을 떠올릴 수 있을까..