문제 정보
백준 ( BOJ ) 11053 가장 긴 증가하는 부분 수열
문제 풀이 : map / dp
문제 출처 : https://www.acmicpc.net/problem/11053
시작 Thinking
이 문제는 정석 풀이는 dp 이지만,
dp로 할 경우 은근 시간을 잡아 먹는 문제 입니다.
처음부터 쭉 탐색을 해 줘야 하기 때문이죠.
dp랑 비슷하지만, map을 사용하면 조금 더 시간 절약이 가능 한 문제 입니다.
예를들어, 9 3 2 1 3 2 1 3 2 1
을 보겠습니다.
3 -> map : (3,1)
2 -> map : (2,1) , (3,1)
1 -> map : (1,1), (2,1), (3,1)
3 -> map : (1,1), (2,1), (3,2)
2 -> map : (1,1), (2,2), (3,2)
1 -> map : (1,1), (2,2), (3,2)
3 -> map : (1,1),(2,2),(3,3)
2 -> map : (1,1),(2,2),(3,3)
1 -> map : (1,1),(2,2),(3,3)
위 방식으로 풀어 주시면 됩니다.
방법은 간단합니다. 앞의 수가 뭐든지 상관은 없습니다.
다만 해당값보다 작은 key의 value 중 최대치를 뽑고, +1 해주면 됩니다.
물론, 해당 key가 있을 경우엔, 수정을,
해당 key가 없을 경우에는 삽입을 해 주면 됩니다 .
코드
#include <iostream>
#include <map>
using namespace std;
int main() {
int n,temp,best;
cin >> n;
map<int, int> m;
for (int i = 0; i < n; i++) {
cin >> temp;
best = 0;
for (auto iter = m.begin(); iter != m.end() && iter->first < temp; iter++) {
if (iter->second > best)
best = iter->second;
}
auto find = m.find(temp);
if (find != m.end()) {
if (find->second < best+1)
m[temp] = best+1;
}
else {
m.insert(make_pair(temp, best+1));
}
}
for (auto iter = m.begin(); iter != m.end(); iter++) {
if (iter->second > best)
best = iter->second;
}
cout << best;
return 0;
}
… 아 근데,, 풀고 보니,
굳이 map을 사용 할 필요도 없고,
배열을 사용해서 풀어주면 훨씬 간단한…;;;
그런데, 배열을 사용하면 시간이 좋지 못하기 때문에..
할거라면 셋도 같이 만들어서, 체크를 해야 하긴 하니 뭐..
비슷 하겠네요
배열 풀이
#include <stdio.h>
using namespace std;
int main() {
short n = 0;
short temp = 0;
short best = 0;
short m[1001] = { 0, };
short result = 0;
scanf(" \n%hd", &n);
for (short i = 0; i < n; i++) {
scanf(" \n%hd", &temp);
best = 0;
for (short i = 0; i < temp; i++) {
if (m[i] > best)
best = m[i];
}
if (m[temp] < best+1)
m[temp] = best+1;
if (result < best + 1)
result = best + 1;
}
printf("%d", result);
return 0;
}