https://www.acmicpc.net/problem/10126
문제 요약
- 앞/뒤에 숫자가 적혀진 카드가 주어짐(0 ~ 10^7, 20만)
- 관객이 카드 두 곳의 위치를 맞교환함(100만번) ==> 이때 상태가 누적됨!
- 관객이 뒤집을때마다 마술사가 적절히 뒤집어서 비내림차순 수열을 만들수 있는지(TAK), 없는지(NIE) 판단
접근법
- 처음에는 뒤집는 사건이 단편적으로 발생하는 것으로 접근해서 틀렸음. 뒤집는 사건은 계속 누적해서 카드의 상태에 영향을 주는 것임
- 일단 카드 앞/뒤는 의미가 없어서 작은 것을 앞, 큰 것을 뒤로 맞춰줌
- 끝과 끝으로 수열이 가능한지 + 구간트리 + 병합기법
- 특정 구간에 대해서 다음과 같이 생각함
- [0][0] : 작은 것 - 작은 것으로 수열이 가능한지
- [0][1] : 작은 것 - 큰 것
- [1][0] : 큰 것 - 작은 것
- [1][1] : 큰 것 - 큰 것
- 구간의 merge도 가능함
- [0][0] 과 [1][0]을 합친다고 할때
- 왼쪽 끝 카드가 3/5, 오른쪽 끝 카드가 2/7 이면
- 왼쪽은 3으로 끝나는 것이 가능, 오른쪽은 7로 시작하는 것이 가능, 그리고 3 <= 7이므로 둘을 합치는것도 가능
-[0][0] + [1][0] = [0][0] 이 가능
- [1][1] 과 [0][1]을 합친다고 하면, 5 >= 2이므로 합치는 것은 불가능
- 모든 경우의 수에 대해 merge해서 구간 결과를 얻어낼 수 있음
- 물론 합치기 전에 한쪽 구간이 되는지 안되는지 판단은 하고 넘어가야함
- [0][0] 과 [1][0]을 합친다고 할때
- merge를 이용하면 init, update도 가능함
- a, b 위치 교환이 발생하면
- a 카드를 b 값으로 대체한 후
- update + merge 수행
- b 도 마찬가지 처리
- 전체 구간에 대해서 [0][0], [0][1], [1][0], [1][1] 중 하나라도 가능한 것이 있으면 수열이 가능한지 판단 가능함
틀렸던 지점
- 문제를 잘못 이해 : 카드 상태가 누적되는데 각각의 사건으로 생각
- 이때는 구간을 3개로 나눈 후 각각을 병합하는 방식으로 접근했는데
- 생각해보니 지금 접근한 것처럼 업데이트 후 전체 구간을 판단하는게 더 괜찮은 것 같음
- merge할때 함수 인자/응답으로 vector<vector> 를 주고 받고 했는데 되게 오래걸림 => char [][] 인자를 주고 받는 방식으로 해결
- char a[2][2]에 대해서 memset()할때 오류가 발생 => size를 측정하니 8로 나옴. => 일일이 초기화하는 방법으로 바꿈
- 기타 또 틀렸던 지점이 있었음.
후기
- 구간트리 테크닉에서 특성을 제대로 활용하는 문제여서 인상깊음
- 전에도 비슷하게 병합, 분해를 이용해서 접근하는 방식이 있었는데 또 깨닫게 되었음
newbieski