일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- 레지스터
- Codeforces Round 831 (Div. 1 + Div. 2)
- vue3
- iupc
- django
- Round 866
- list_display
- 리버싱
- 넥토리얼
- Good Bye 2022: 2023 is NEAR
- shake!
- idpiframe_initialization_failed
- Div. 2
- 카카오 API
- dart
- 밑바닥부터 시작하는 딥러닝 1
- 인하대 프로그래밍 경진대회
- 코드포스
- 알고리즘 대회
- Graph Cost
- 앳코더
- 2022
- Hello 2023
- Flutter
- E - Hanging Hearts
- expand item
- 1557
- vue-google-login
- 기본키 변경
- 카카오 로그인
- Today
- Total
pseong
Educational Codeforces Round 149 (Rated for Div. 2) F. Editorial for Two 본문
Educational Codeforces Round 149 (Rated for Div. 2) F. Editorial for Two
pseong 2023. 6. 4. 23:07Problem - F - Codeforces
codeforces.com
F번 치곤 쉽게 나와서 진짜 오랜만에 F번을 풀어봤다.
가장 안좋은 방법은 k개를 선택하고 k개를 차례대로 순회하면서 답을 구하는 방법이다.
이 방법은 O(nCk * k) 시간 복잡도 이므로 말도 안되는 시간이 걸린다.( 대략 30만 팩토리얼 )
k개를 선택하는 방법은 괸장히 비효율적이므로 다른 방법을 생각해 내야 한다.
답은 문제의 정의를 다르게 하면 된다. 디스크립션에서 k개를 선택하고 분할해서 계산한다. 우리는 분할 먼저 하고 k개를 선택할 것이다. ( 생각해 보면 이 풀이가 떠올리기 어렵지 않은 이유가, 연산의 순서를 바꾸는 방법은 흔한 풀이 방법중에 하나이기 때문일 것이다. ) 분할 먼저 하고 왼쪽에서 d개, 오른쪽에서 k-d개를 선택해서 답을 구해주면 된다. 이 풀이의 시간 복잡도는 O(nnlogn) 이므로 풀이에 적합하지 않은 시간 복잡도 이지만 처음처럼 막무가네인 시간복잡도는 아니다.
여기에서 이분탐색을 적용하면 시간복잡도를 줄일 수 있다. 정답이 특정 값 기준으로 가능, 불가능이 나뉘므로 이분탐색을 사용할 수 있다. 정답이 x보다 작거나 같은지 O X 를 결정하는 결정 문제로 바꾸면 된다는 이야기이다. 여기까지가 O(nlogk) 이다. 여기서 왼쪽 구간과 오른쪽 구간을 각 각 정렬하게 되면 nlogn이 붙어서 O(nnlogklogn) 이 되어버린다. 따라서 정렬을 사용할 수 없다. 여기서 시간복잡도를 줄일 수 있는 아이디어가 다이나믹 프로그래밍이다. 이전에 구했던 값을 재사용 하면서 구하면 O(nlognlogk) 만에 답을 구할 수 있다. 만약 분할을 먼저 하고 이분탐색을 시도하게 되면 이분탐색 시 이전에 사용한 값을 재사용 할 방법이 없기 때문에 잘못된 풀이다. 이분탐색을 먼저 하고 분할을 하게 된다면 우선순위 큐를 사용하여 풀이할 수 있다. 배열에서 총 합이 x보다 작거나 같은 원소 수의 합이 최대인 그룹의 원소의 개수를 접두사 배열과 접미사 배열 두 개에서 각 각 nlogn 만에 구할 수 있다. 그룹에 원소를 하나 추가하고 그룹에서 가장 큰 값을 하나씩 빼가면서 그룹이 합이 x보다 작거나 같아질 때 까지 빼면 된다. 원소가 n번 추가될 수 있으므로 우선순위 큐로 관리한다면 O(nlogn) 시간복잡도로 접미사 배열과 접두사 배열을 만들 수 있다. 그리고 나서 구간을 나눠 가면서 가능한지 판단하면 된다. 따라서 시간 복잡도는 O(logk(nlogn + n)) 이므로 결론적으로 O(nlognlogk) 시간복잡도가 도출된다.
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
Codeforces Round 831 (Div. 1 + Div. 2) E - Hanging Hearts (1) | 2023.06.10 |
---|---|
Codeforces Round 866 (Div. 2) D. The Butcher (1) | 2023.05.31 |
Codeforces Round #841 (Div. 2) E. Graph Cost (1) | 2023.01.08 |
Hello 2023 E. Anya's Simultaneous Exhibition (0) | 2023.01.07 |
Hello 2023 (2) | 2023.01.04 |