-
[백준] #14003 가장 긴 증가하는 부분수열5 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 22:17
문제
https://www.acmicpc.net/problem/14003
14003번: 가장 긴 증가하는 부분 수열 5
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
목표
무작위로 주어진 배열에서 증가하는 부분수열중 가장 긴 수열을 찾는다.
풀이
배열하나를 만들어 값들을 읽어나가면서 그 값이 들어갈 수 있는 위치와 그 값을 새로운 배열에 저장한다.
이렇게 하는 이유는 모든 탐색이 끝난후 해당 수열을 출력할때 알맞은 값을 찾기위함이다.
즉 값이들어갈 위치 인덱스가 섞이더라도, 나중에 출력시 알맞은 인덱스의 값을 출력하기 위함이다.
코드
#include <iostream> #include <algorithm> #include <stack> #define MAX 1000001 using namespace std; int N; //주어지는 값들을 저장할 배열 int arr[MAX]; //증가부분수열을 저장 할 배열 => 정확한 배열은 파악 불가능 int lis[MAX]; //정확한 배열을 확인하기위해 증가하는부분수열에 들어갈 인덱스번호와 값을 저장할 배열 pair<int, int> dp[MAX]; //증가하는부분수열의 크기 int cnt = 0; stack<int> s; void func() { //첫번째 값 세팅 dp[0].first = 0; dp[0].second = arr[0]; lis[cnt++] = arr[0]; for (int i=1; i<N; ++i) { //새로읽은 값이 기존 수열의 마지막값보다 큰경우 //수열배열에 삽입한다. 인덱스와 값을 dp에 저장한다. if (lis[cnt-1] < arr[i]) { lis[cnt] = arr[i]; dp[i].first = cnt++; dp[i].second = arr[i]; } //새로읽은 값이 기존 수열의 마지막값보다 작은 경우 //알맞은 수열배열위치에 삽입하고, 인덱스와 값을 dp에 저장한다. else { int pos = lower_bound(lis, lis + cnt-1, arr[i]) - lis; lis[pos] = arr[i]; dp[i].first = pos; dp[i].second = arr[i]; } } for (int i=0; i<N; ++i) { cout << dp[i].first << " " << dp[i].second << '\n'; } cout << cnt-- << '\n'; for (int i=0; i<=cnt; ++i) { cout << lis[i] << " "; } cout << '\n'; //총 개수를 나타내는 인덱스와 비교하며 차례차례 인덱스를 줄여가며 알맞은 값을 찾는다. for (int i=N-1; i>=0; --i) { if (dp[i].first == cnt) { s.push(dp[i].second); cout << dp[i].first << " " << dp[i].second << " push" << '\n'; cnt--; } } while (!s.empty()) { cout << s.top() << " "; s.pop(); } } int main() { cin >> N; for (int i=0; i<N; ++i) { cin >> arr[i]; } func(); // cout << cnt << '\n'; // for (int j=0; j<cnt; ++j) // cout << lis[j] << " "; // cout << '\n'; }
'Algorithm > 알고리즘 백준 풀이' 카테고리의 다른 글
[백준] #1102 발전소 - (DP) (0) 2020.03.14 [백준] #11062 카드게임 - (DP) (0) 2020.03.11 [백준] #11049 행렬 곱셈 순서 - (DP) (0) 2020.03.02 [백준] #19115 가장 큰 정사각형 - (DP) (0) 2020.03.02 [백준] #9252 LCS2(Longest Common Subsequence) - (DP) (0) 2020.03.02