[백준알고리즘] 11053번: 가장 긴 증가하는 부분 수열 -C++

[백준알고리즘] 11053번: 가장 긴 증가하는 부분 수열 -C++

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

11053번: 가장 긴 증가하는 부분 수열

말 그대로 주어진 수열 중에서 원소의 순서를 변경하지 않고 증가하는 수열을 만들 때 만들 수 있는 가장 긴 수열의 길이를 구하는 문제다.

 

예전에 파이썬으로 푼 적이 있던 문제다. 이때 코드를 보니까 훨씬 쉽게 풀었던 것을 알 수 있다. C++로도 이 방식으로 풀어도 쉽게 통과할 수 있을 것 같다. 단, Python에서는 ":"를 통해서 쉽게 수열을 파싱 할 수 있었던 것과 다르게 이중 for문을 돌려서 풀면 될 것 같다.

[백준알고리즘] 11053번: 가장 긴 증가하는 부분 수열 -Python (tistory.com)

[백준알고리즘] 11053번: 가장 긴 증가하는 부분 수열 -Python

 

오늘은 위에서 예전에 풀었던 방식대로 풀지 않았다. 사실 오늘 푼 코드가 조금은 더 복잡하다. 얼마 전에 이와 비슷한 다른 문제에 달린 댓글을 확인하면서 글을 다시 읽다가 해당 문제에 대한 풀이를 본 적이 있다. 그러다 보니까 그 기억으로 그 방식대로 푼 것 같다. 처음에는 DFS 방식으로 브루트포스를 돌렸다가 당연하게도 시간 초과가 발생했다.

 

풀고 나니 굉장히 내 풀이와 같은 방식으로 풀으신 분의 좋은 글이 있어 첨부한다. 예전 글에 달린 댓글로 확인한 문제도 이와 같은 방법으로 문제를 해결했었다. 그런데 이분의 해설이 더 깔끔하기 때문에 아래에 해당 블로그 링크를 첨부했다.

[백준] 11053번 C/C++ 풀이 _ 가장 긴 증가하는 수열 - Easy is Perfect (melonicedlatte.com)

[백준] 11053번 C/C++ 풀이 _ 가장 긴 증가하는 수열 - Easy is Perfect

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제에 필요한 것은 "길이"다.

 

그렇기 때문에 수열을 구하는 중간에 말이 안 되는 수열이 있어도 상관이 없는 것이다. 그렇기 때문에 위의 참고 링크에서 다룬 방식으로도 문제를 풀 수 있는 것이다.

 

하나의 원소를 포함할 때마다 그 원소가 들어갈 위치를 찾는다. 각 원소는 다음과 같은 두 개의 행동을 취하게 된다.

1. 생성되는 수열의 맨 뒤에 삽입
2. 수열을 이루고 있는 원소의 자리로 삽입(교체)

 

1번의 경우에는 생성되는 수열이 비어있는 경우와 생성되는 수열의 마지막보다 더 큰 수가 삽입될 때 취하는 행동이다. 기존 값들보다 더 큰 값이 수열에 추가되는 것이기 때문에 그저 맨 뒤에 삽입하면 된다.

 

2번의 경우에는 삽입되는 위치를 주목해야 한다. 해당 값이 \( X \)라면, \( X \)가 삽입되는 위치의 왼쪽에는 \( X \) 보다 작은 값들만 위치하게 된다. 즉, \( X \) 보다 큰 값 중 가장 작은 값의 위치에 \( X \)가 삽입된다. 예를 들어보겠다.

생성되는 수열이 현재 [10, 20, 30]이며 새로 삽입할 수가 15라면, 20을 15로 대체한다.
즉, [10, 15, 30]이라는 수열이 된다.

 

이렇게 된다면, [10, 15, 30]은 [10, 20, 30]으로 인해 현재 최대 길이가 3인 것을 유지하면서 [10, 15]로 새로운 수열을 만들어갈 준비도 하게 되는 것이다.

 

만약 이후에 17과 20이 삽입되는 수로 나타난다면, [10, 20, 30]이라는 수열의 뒤에는 추가할 수 없다. 하지만, [10, 15] 수열의 뒤에는 삽입될 수 있어 [10, 15, 17, 20]의 새로운 수열로 수열의 최대 길이를 갱신하게 된다.

 

이를 위해서 해당 위치에 값을 대체하는 것이다. 이렇게 이전에 생성된 수열에 따라서 다음 수열이 결정되기 때문에 동적계획법(Dynamic Programming)으로 분류된 문제다.

 

아래는 위의 과정들을 C++로 풀이한 코드다.

#include <iostream>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

void insert(std::vector<int>& sequence, int num)
{
	if (sequence.empty() || sequence.back() < num)
	{
		sequence.push_back(num);
		return;
	}

	for (int i = sequence.size() - 2; i >= 0; i--)
	{
		if (sequence[i] < num)
		{
			sequence[i + 1] = num;
			return;
		}
	}

	sequence[0] = num;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> arr(n);
	for (int i = 0; i < n; i++)
		std::cin >> arr[i];

	std::vector<int> sequence;

	for (int i = 0; i < n; i++)
		insert(sequence, arr[i]);

	std::cout << sequence.size();
}

 

---

[참고]

[백준] 11053번 C/C++ 풀이 _ 가장 긴 증가하는 수열 - Easy is Perfect (melonicedlatte.com)

[백준] 11053번 C/C++ 풀이 _ 가장 긴 증가하는 수열 - Easy is Perfect