코드 포스(Code Force) 1075 - C. The Tower is Going Home

문제 유형: 그리디

문제 URL: https://codeforces.com/contest/1075/problem/C

  문제를 간단히 요약하자면 다음과 같습니다.

  높이고 10^9이고, 너비가 10^9인 체스판이 있습니다. 이 때 가장 왼쪽 아래인 (1, 1)의 위치에 하나의 돌이 있습니다. 얘는 마차(Look)라서 이동할 때 상하좌우로 쭉쭉 이동할 수 있습니다. 이 돌은 체스판의 가장 위쪽에 도달하고자 합니다. y 좌표 상으로 10^9의 위치에 닿으면 되는 것이며 x 좌표는 어떤 값이 들어가도 상관 없습니다. 좌표를 나타낼 때는 (열, 행)과 같은 방식으로 표현합니다.

  이 때 체스판을 가로 막는 다양한 선들이 있다고 합니다. 선의 종류로는 수직선과 수평선이 있습니다.

  1) 수직선: 특정한 x 위치에서 수직으로 끝 없이 이어진 선입니다.

  2) 수평선: x1부터 x2까지의 열을 차지하는 선으로, 행 y에 위치합니다.

  수평선들은 수직 관계에 있는 다른 선들과는 x 좌표가 겹쳐도 됩니다. 하지만 수평한 수평선끼리는 x 좌표가 겹치지 않는다고 합니다. (1, 1)에 위치한 돌은 y 좌표 상으로 10^9의 위치에 닿을 때까지 이동할 수 있는데, 체스판에 있는 선들을 뚫고 나아갈 수 없다고 합니다. 따라서 선으로 가로 막힌 경우 선을 지우고 나아가야 합니다. 체스판의 가장 위쪽까지 도달하도록 선을 삭제할 때 최소한의 삭제할 선 개수를 구하면 됩니다.

※ 핵심 풀이 ※

  이 문제는 두 개의 사실만을 깨달으면 쉽게 풀 수 있고, 깨닫지 못하면 푸는 것이 굉장히 어렵습니다.

  ▶ 그것은 바로 수평선 중에서 왼쪽 x 좌표가 1이 아닌 것은 무시해도 된다는 것입니다.

  ▶ 그로 인해 수평선의 y 좌표는 신경 쓸 필요가 없다는 것까지 유추하면 됩니다.

  수평선의 왼쪽 x 좌표가 1이 아닌 것은 무시해도 좋은 이유를 설명해드리겠습니다. 이것은 '수평한 수평선끼리는 x 좌표가 겹치지 않는다'는 성질 때문에 가능한 것입니다.

  다음과 같은 경우를 생각해봅시다.

  몇 개의 선을 삭제해야 제일 위 칸으로 이동할 수 있을까요?

  정답은 바로 1개의 선입니다.

  위와 같이 중간에 있는 선을 지워버리면, 지그재그로 이동하여 제일 위 칸까지 이동할 수 있거든요. 결과적으로 왼쪽 x 좌표가 1인 수평선이 아니면 사실상 전혀 의미 없는 수평선이라고 할 수 있습니다. 돌 입장에서는 왼쪽 끝까지 편하게 이동할 수 있으니까요.

  결과적으로 기존의 시작할 때의 상태는 왼쪽 x 좌표가 1이 아닌 수평선들은 모두 지워버린 위 그림과 같은 상태와 같다고 볼 수 있습니다. 이렇게 정리된 상태에서 보니 한 가지 더 알게 되는 점이 있습니다. 그것은 바로 y 좌표는 굳이 신경 쓸 필요가 없다는 것입니다. 왜냐하면 어차피 하나의 y 좌표에는 최대 1개의 수평선만이 존재할 수 있을 테니까요. y 좌표는 고려 할 필요가 없습니다.

  이러한 원리를 이용하여, 각 수직선을 왼쪽부터 차례대로 확인하며 위를 덮는 수평선의 개수를 고려하여 정답을 도출하면 됩니다.

※ 예시 입출력 ※

input

Copy

2 3
6
8
1 5 6
1 9 4
2 4 2

output

Copy

1

input

Copy

1 3
4
1 5 3
1 9 4
4 6 6

output

Copy

1

input

Copy

0 2
1 1000000000 4
1 1000000000 2

output

Copy

2

input

Copy

0 0

output

Copy

0

input

Copy

2 3
4
6
1 4 3
1 5 2
1 6 5

output

Copy

2

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include 
#include 
#define MAX 100001

using namespace std;

int vertical[MAX], line[MAX];
int INF = 1e9;

int main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> vertical[i];
	vertical[n++] = INF;
	sort(vertical, vertical + n);
	int lineCount = 0;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c; 
		if (a != 1) // 왼쪽 x 좌표가 1인 수평선은 무시
			continue;
		line[lineCount++] = b;
	}
	sort(line, line + lineCount);
	int res = lineCount; // 시작 위치에서 돌이 위쪽으로만 뚫고 이동하는 경우를 초기 값으로 설정 
	int j = 0;
	// 각 수직선을 왼쪽부터 하나씩 확인하며 
	for(int i = 0; i < n; i++) {
		// 각 수직선을 덮는 수평선들의 개수를 세기 
		while (j < lineCount && line[j] < vertical[i]) {
			j++;
		}
		res = min(res, i + lineCount - j);
	}
	cout << res;
	return 0;
}