[883J] Renovation

링크 : http://codeforces.com/contest/883/problem/J

 풀이는 생각보다 금방 떠올렸는데 구현하면서 실수를 너무 많이 해서 계속 틀렸다. 대회였으면 못 풀었을 것 같다. 생각을 좀더 엄밀하게 정리하고 증명한 다음에 코드를 짜는 습관을 들여야 하는데 매번 그게 잘 안되는 듯. 더 신경써야 할 것 같다.

 문제 요약:

 m개의 철거 예정인 빌딩이 있다. n일동안 철거를 진행할텐데, 빌딩을 철거하는데에는 비용이 든다. pi = i번째 빌딩을 제거하는데 필요한 비용. 그리고 n일동안 날마다 철거를 위한 지원금 ai가 들어온다(ai=i번째 날에 받은 지원금). 여기에 추가적으로 bi라는 변수가 빌딩마다 하나씩 주어지는데, i번째 날에 j번째 빌딩을 제거하기 위해서는 bj <= ai라는 조건을 만족해야 한다. 이 때 n일동안 철거할 수 있는 최대 빌딩 개수를 구하는게 문제. 조건만 만족되면 하루에 빌딩을 몇 개라도 철거할 수 있다. 1 <= n, m <= 100,000 이고 1 <= ai, bi, pi <= 10^9

 만약에 어떤 빌딩 k를 i번째 날에도 철거 가능하고 j번째 날에도 철거 가능하다면(bk <= ai, bk <= aj), 그리고 i <= j라면 해당 빌딩을 j번째 날에 철거하는 게 더 이득이다. 왜냐하면 j번째 날에 지원금이 더 많이 모여서 돈이 더 많으니까, 판단할 수 있는 여지가 더 넓어지기 때문. 따라서 우선 빌딩을 제거할 수 있는 데드라인을 구해보자.

 각 빌딩의 데드라인은 빌딩들을 b 값 오름차순 기준으로 정렬하면 O(MlogM + N) 시간 내에 구할 수 있다. 빌딩들을 먼저 b값으로 정렬해두고, 맨 마지막 날짜부터 확인해보자. 이 때 맨 앞에서부터 b값이 an값 이하인 빌딩들은 전부 다 데드라인이 n번째 날이다. 이제 다시 n-1번째 날로 이동해서, 만약에 그 날짜의 지원금 a가 n번째 날의 지원금보다 값이 더 작다면 n-1번째 날에 철거할 수 있는 빌딩들은 모두 n번째 날에도 철거할 수 있는 빌딩들이다. 따라서 이 날이 데드라인인 빌딩은 없다. 만약에 이 날의 지원금이 n번째 날의 지원금보다 크다면, b값이 n번째 날의 지원금보다 크고 n-1번째 날의 지원금이하인 빌딩들은 모두 해당 날짜가 데드라인이 된다.

 이런 식으로 아직 데드라인을 못 고른 빌딩을 b가 제일 작은 값부터 순서대로, 맨 마지막 날짜에서부터 확인하면서 데드라인을 정해주면 된다. 

 데드라인을 구하고 나면 이제 각 빌딩을 무조건 데드라인 날짜까지 철거하는 걸 미뤄놨다가 철거하면 된다고 생각할 수 있다. 이 때 정해진 비용 내에서 최대한 많은 빌딩을 제거하려면 빌딩 철거 비용 p가 제일 작은 건물부터 철거해야한다. 그러면 이제 p가 제일 작은 값부터 순서대로 빌딩을 다시 정렬해주자. 이제 p가 제일 작은 빌딩부터 순서대로 확인하면서 해당 빌딩을 철거할 수 있는지 아닌지 확인해주면 된다.

 해당 빌딩을 철거할 수 있는 데드라인 날짜에서 남은 지원금이 해당 빌딩의 철거 비용 p이상이면 철거 가능하고, 그렇지 않다면 철거할 수 없는 빌딩이다(당연히). money[i] = 1~i번째 날짜까지 지원금 합, used[i] = 1~i번째 날짜까지 사용한 철거 비용 이라고 정의하면, i번째 날짜 시점에서 남은 지원금은 money[i] - used[i]라고 볼 수 있다. 하지만 이 때 빌딩을 무조건 데드라인 기준으로 철거하고 있고 빌딩들을 데드라인 순으로 정렬해서 보고 있는 게 아니기 때문에, 이것만 가지고는 부족하다. p[i] < p[j] 인데 deadline[i] > deadline[j]인 빌딩이 있는 경우, 그리고 이 빌딩을 철거한 경우 i번째 날짜 이후에 해당 빌딩을 철거해줄 것이기 때문에 이 빌딩을 철거하기 위한 비용을 i번째 날짜까지 번 돈에서 끌어다 쓰는 경우가 생길 수 있다(이후에 써야되기 때문에 안 쓰고 남겨둬야하는 돈 개념).

 이 비용은, 마지막으로 빌딩을 철거한 날짜가 last라고 했을 때 money[last] - money[i] 보다 used[last] - used[i]가 더 큰 경우, (used[last] - used[i]) - (money[last] -money[i]) 라는 식으로 구할 수 있다. i+1번째 날짜부터 last번째 날짜까지 번 돈보다 i+1번째 날짜부터 last번째 날짜까지 쓴 돈이 더 많은 경우 그 차이만큼은 1~i번째 날짜에서 번 돈에서 충당해야 하기 때문이다. 따라서 money[i]가 이 두 비용을 모두 합한 값 + 현재 빌딩의 철거 비용 p 이상이라면 이번 빌딩을 철거할 수 있고, 그렇지 않다면 철거할 수 없다. 이 과정을 모든 빌딩에 대해 반복해주면 된다. 

 이 때 money[i]값은 누적합으로 O(N)시간에 구할 수 있고, used[i]값은 매 빌딩을 철거할 때마다 값이 계속 바뀌어야 하고 1~i번째까지의 부분합을 구해야하기 때문에 펜윅트리를 이용해서 구해야 한다. 따라서 이 부분 순회 및 used 갱신에서 O(MlogN)의 비용이 들고, 앞서 데드라인 계산하는데 필요한 시간까지 합하면 전체 시간 복잡도는 O(Mlog(M + N))이 된다.