https://www.acmicpc.net/problem/34156
문제요약
- 바게트 (s, e) 주어짐, e-s>=2, N 10만개
- 다른 바게트에 완전히 포함되면 삭제
- 2이상 걸치면 칼질 가능
- 바게트가 한번 이상 칼질이 되도록 하는 최소 칼질 횟수
접근법
- 더 짧게 구현도 가능한 것 같은데, 내가 접근한 방법을 적어보려고 함
- 두 개의 방안을 마련해야함
- 다른 바게트에 포함되는지 여부
- 칼질이 두 바게트 이상에 적용되는지 여부
- 다른 바게트에 포함되는지
- 정렬1 : 시작길이가 앞서는 것, 길이가 긴 것 기준
- 정렬2 : 종료 위치 순서대로 정렬
- 정렬1은 큰 바게트, 정렬2는 작은 바게트(포함될)를 의미
- 가장 큰 바게트에서(정렬1기준), 작은 바게트들을 살펴보고(정렬2기준) 포함이 되는지 판단
- 정렬1은 어짜피 가장 큰 바게트이고, 정렬2는 끝 위치 기준으로 탐색을 해나가기 때문에 벗어나면 다시 새로운 바게트를 탐색
- 완료 목록, 삭제 목록을 업데이트함
- 칼질이 두 바게트 이상에 적용되는지
- 앞에서 제거해야할 바게트는 다 제거 완료된 상태
- 가장 긴 바게트의 마지막위치 - 1을 기준으로 다른 바게트가 같이 잘릴 수 있는지 판단한다.
- 정렬1 기준으로 바게트를 탐색
- "바게트 마지막 위치 - 1" 값을 기억
- 다음 나오는 바게트들이 포함하는지를 판단
- 포함하면 계속 진행
- 포함하지 않으면 새로운 바게트 => 왜냐면 이후 바게트들은 기존 긴 바게트로 커버가 안됨
- 두 로직을 합치면 될 것 같은데 잘 안되서 나눠서 구현함
newbieski