티스토리 뷰
11997번: Load Balancing (Silver)
Farmer John's \(N\) cows are each standing at distinct locations \((x_1, y_1) \ldots (x_N, y_N)\) on his two-dimensional farm (\(1 \leq N \leq 1000\), and the \(x_i\)'s and \(y_i\)'s are positive odd integers of size at most \(1,000,000\)). FJ wants to par
www.acmicpc.net
1. N은 기껏해야 1000이지만, 좌표 범위가 1e6이므로 좌표 압축을 해서 위치를 다시 그리는 과정이 필요함. 중복을 지우는 데에 set을 이용했음.
2. 이제 네 부분으로 잘라야 되는데, 자르는 위치를 정하고 각 부분을 다 탐색하면 O(N^2) * O(N^2)으로 반드시 시간초과가 남. 누적합을 이용하여 O(N^2)을 O(1)으로 처리해야함.
3. 어떻게 잘라야 되는지만 잘 정의하면 문제 해결됨. pSum[i]를 항상 맨 처음부터 i개를 고려했을 때의 합으로 정의해야 문제 해결이 편한 경우가 많음. 아무것도 포함시키지 말아야 하는 경우를 처리할 때 유리한데, pSum[0]가 아무것도 포함하지 않은 경우를 의미함.
- Source code link
github.com/Bibidi/Algorithms/blob/master/boj/boj%2011997.cpp
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 디지털 비디오 디스크
- 백준 2336
- 백준 9345
- boj 10775
- boj 1106
- 백준 1280
- 제로베이스 백엔드 스쿨
- boj 9345
- 백준 16562
- boj 14868
- Ugly Numbers
- boj 12713
- boj 16562
- 제로베이스 스쿨
- boj 3006
- 터보소트
- 백준 3006
- 백준 10775
- 인간 대포
- 부트 캠프
- 사탕상자
- boj 2243
- boj 1280
- 백준 1106
- 백준 2243
- boj 2336
- 백준 14868
- 백준 12713
- 백준 10473
- boj 10473
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함