[ICPC 본선 대비 뇌셋] Day 2

백준 5258번 trapezoid www.acmicpc.net/problem/5258

5258번: trapezoid

문제해석이 틀릴것을 우려한 레프가 문제를 설명해주셨다..

[풀이] independent set을 구하는 문제인데, 구간보다 조금 더 꼬아놓은 셋이라는 특징이 있다. 

 

사다리꼴이 겹치지 않을 조건을 생각하면 되는데, 사다리꼴 A의 오른쪽 점들의 x좌표들이 사다리꼴 B의 왼쪽 점들의 x좌표들보다 각각 작으면 된다. 이러면 2차원상에 점을 올려놓을 생각을 할 수 있다. 각 사다리꼴을 2차원 상에서 (a,c) -> (b,d)의 화살표로 생각한다. (a,c)를 시작점, (b,d)를 끝점이라고 부르자.

I번째 사다리꼴이 제일 오른쪽에 포함되는 독립 사다리꼴의 최대 개수를 A[i]라고 하면,

A[i] = max(A[j] : j번째 사다리꼴의 끝점의 좌표가 각각 모두 i번째 사다리꼴 시작점 좌표보다 작거나 같다)

즉, 원점을 한 꼭짓점으로 하고 축과 평행한 직사각형 내부의 최댓값을 구하는 쿼리로 바뀌고, 이는 Segment Tree로 구할 수 있다.

 

[코딩] 시작점으로 pii 소팅하고, pst로 각 점의 A값을 구한다.

 

시간복잡도: O(NlgN)

 

이번 문제는 앞 문제보다는 좀 쉽게 풀린 것 같다.

복잡해보여도 간단한 상황으로 바꿀 수 있는 문제는 이제 어느정도 풀 수 있는듯? 근데 그게 쉽지 않은 문제들은 아직 정말 어렵다. 특히 솔브닥 기준 다이아 3정도 난이도부터는 나에게 많이 어려워지는것 같다. 매일 풀면서 감을 끌어올려야지.

백준 1868 보물찾기 https://www.acmicpc.net/problem/1868

1868번: 보물찾기

답이 lg(트리의 지름)인것을 쉽게 유추할 수 있고, 그것이 정답이 아님을 또한 쉽게 확인할 수 있다.
[증명]
1. 답>=lg(트리의 지름)
트리 지름 상에 답이 있다고 가정하자. 각 쿼리에 대해서 남은 지름의 절반 이상이 있는 방향을 선택해주면 된다.

2. 답<=lg(트리의 지름)
망