[백준알고리즘] 2565번: 전깃줄 -C++

[백준알고리즘] 2565번: 전깃줄 -C++

2565번: 전깃줄 (acmicpc.net)

2565번: 전깃줄

주어진 전깃줄 중에서 최소의 전깃줄을 제거해 겹치는 선이 없게 만드는 문제다.

 

예전에 파이썬으로 풀었던 적이 있는 문제다. 예전에 풀었던 코드를 보니 '역시 파이썬은 코드가 쉽구나'라는 생각과 동시에 '이때는 왜 이리 쉽게 푼 것 같지..'라는 생각이 들었다. 그만큼 오늘 바로 풀어내지는 못했었다.

[백준알고리즘] 2565번: 전깃줄 -Python (tistory.com)

[백준알고리즘] 2565번: 전깃줄 -Python

 

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

 

---

 

처음에는 문제를 풀었을 때는 틀렸다. 처음에는 A에서 B로 연결된 전깃줄을 A의 번호대로 오름차순 시킨 뒤, 이전 연결되었던 전깃줄에서 가장 높은 B의 번호를 유지했다. 이 번호보다 큰 수가 나올 때만 카운트를 늘려줌으로써 A에서 B로 연결될 때 겹치지 않는 전깃줄의 수를 구하도록 했다. 이후 마찬가지 방법으로 B에서 A로 연결되는 전깃줄도 구해줌으로써 발생 가능한 문제를 없애려고 했다.

 

하지만, 해당 방법에는 문제가 있었다. 반례를 아무리 생각해도 안 나오다가 게시판을 통해서 찾게 되었다.

5
3 4
1 5
4 2
2 3
5 1

// output = 3
// 2개의 선 (2, 3), (3, 4)를 제외한 세 개의 선을 지운 것이 정답

 

이 반례가 '이전 연결되었던 전깃줄에서 가장 높은 B의 번호를 유지'를 했던 부분이 잘못된 생각이었음을 알게 해 주었다. 중간부터 누적되는 경우는 점검해주지 못하기 때문이다.

 

그래서 방향을 틀어서 접근했다. 항상 해당 전깃줄을 포함해 겹치지 않는 전깃줄의 수를 누적해서 체크해주는 것으로 이전의 문제를 해결하려 했다. 이는 Longest Increasing Sequence (증가하는 수열) 문제로 볼 수 있다. 따라서 동적계획법 (DP; Dynamic Programming) 문제라고도 볼 수 있다.

 

즉, 문제에서의 입력 예시로 보면 A에 대해 정렬한 상태가 아래와 같다.

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

 

이때 A의 첫 번째 전깃줄부터 증가하면서 이전 전깃줄들을 고려해서 가장 겹치지 않는 누적합을 구해주는 것이다.

 

예를 들어서 1->8의 경우에는 이전에 전깃줄이 없었기 때문에 자신을 포함해 가능한 전깃줄의 수가 1이다.

 

다음 2->2는 이전에 1->8이 있었으나 (2 < 8) 이기 때문에 겹치는 선이다. 따라서 2->2를 포함해 겹치지 않는 전깃줄의 수는 1이다.

 

마찬가지로 3->9는 이전에 1->8과 2->2가 있었다. 이때 각각 확인해줘야 한다. 1->8은 (8 < 9)이기 때문에 3->9와 겹치지 않는 수다. 1->8이 자신을 포함해 겹치지 않는 전깃줄의 수가 1이기 때문에 3->9는 이 1에 1을 더한 2가 겹치지 않는 전깃줄의 수라고 할 수 있다.

또한, 2->2도 (2 < 9)이기 때문에 3->9와 겹치지 않는 수다. 2->2도 자신을 포함해 겹치지 않는 전깃줄의 수가 1이기 때문에 3->9는 기존의 겹치지 않는 전깃줄의 수인 2와 같은 수를 갖는다.

 

마찬가지 방법들로 접근해주면 된다. 그러면 아래와 같은 가능한 전깃줄의 수가 나오게 된다.

1 8		->1
2 2		->1
3 9		->2
4 1		->1
6 4		->2
7 6		->3
9 7		->4
10 10	->5

 

이후 제거해줄 전깃줄의 수는 전체 전깃줄의 수에서 최대로 겹치지 않는 전깃줄의 수를 뺀 값임을 이용해 답을 구해주면 된다.

 

이러한 방식대로 풀어준 C++ 코드다.

#include <iostream>
#include <vector>
#include <algorithm>

void solve(void);

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

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

	std::vector<std::pair<int, int>> lineFromA;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		std::cin >> a >> b;
		lineFromA.push_back(std::make_pair(a, b));
	}

	// first에 대해 오름차순 정렬
	// std::sort(lineFromA.begin(), lineFromA.end(), std::less());
	std::sort(lineFromA.begin(), lineFromA.end());

	std::vector<int> longestIncreasingSequence(n, 0);
	for (int i = 0; i < n; i++)
	{
		int target = lineFromA[i].second;

		int count = 0;
		for (int j = 0; j < i; j++)
		{
			if (target < lineFromA[j].second)
				continue;

			count = std::max(count, longestIncreasingSequence[j]);
		}

		longestIncreasingSequence[i] = count + 1;
	}

	std::cout << n - *std::max_element(longestIncreasingSequence.begin(), longestIncreasingSequence.end());
}

 

---

[참고]

글 읽기 - 2565번 반례좀 찾아주세요ㅠㅠ (acmicpc.net)

글 읽기 - 2565번 반례좀 찾아주세요ㅠㅠ