백준 11997

11997번: Load Balancing (Silver)

 

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