[C++] 백준(BOJ) - 14003 : 가장 긴 증가하는 부분수열 5

02 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 14003 : 가장 긴 증가하는 부분수열 5(링크)

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

알고리즘

1. LIS

풀이

• LIS 배열과 pair<int, int> 형, 그리고 stack을 활용하여 정답 부분 수열 역추적
• lower_bound
  • lis 배열을 len 길이 만큼 돌았을 때, lowerPos가 INF에서 변동이 없다 => 가장 큰 수가 들어옴
  • lowerPos가 현재 수보다 작게 들어옴 => *lowerPos 값 num으로 갱신
• pair<int, int> ans 배열
  • first : 이전 배열을 타고 넘어갈 순서 저장
  • second : 값 저장
• stack
  • ans 배열 끝에서부터 순회하며 len - 1 길이부터 역추적해서 stack에 push
  • top을 pop해 나가며 정답 출력

코드

// BOJ - 14003 : 가장 긴 증가하는 부분 수열 5
#include <bits/stdc++.h>
using namespace std;

int n, lis[1000004], len, num;
pair<int, int> ans[1000004];
stack<int> stk;
const int INF = 1e9 + 4;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	fill(lis, lis + 1000004, INF);
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> num;
		auto lowerPos = lower_bound(lis, lis + len, num);
		int _pos = (int)(lowerPos- lis);
		if (*lowerPos == INF) len++;
		*lowerPos = num;
		ans[i].first = _pos;
		ans[i].second = num;
	}

	cout << len << '\n';
	for (int i = n - 1; i >= 0; i--)
	{
		if (ans[i].first == len - 1)
		{
			stk.push(ans[i].second);
			len--;
		}
	}
	while (stk.size())
	{
		cout << stk.top() << ' ';
		stk.pop();
	}

	return 0;
}

평가

• lower_bound를 활용한 LIS 풀이
• 정답이 되는 부분 수열을 출력하기 위해서는 추가적인 자료구조 필요
  • pair<int,int>, stack