19584 난개발 (누적합,TreeSet)

https://www.acmicpc.net/problem/19584

19584번: 난개발

1.접근

문제의 예시 그림을 보고 고민을 해보면 X축의 값은 필요없고 Y축으로 압축해서 누적합이 가장 큰 곳을 구하면 된다는 생각을 할 수 있다.

통행량을 계속 증가시켜주기 위해서 구간에 대해서 세그먼트 트리도 생각해보고 여러가지 생각해보았지만 y축으로 정렬하여 존재하는 모든 y축을 돌면서 시작지점에는 +,종료지점에는 -를 해주는 방식을 생각했다.

2.풀이

누적합을 어떻게 구할지 생각하는게 중요한 문제이다.

최대값을 구하려면 y축의 좌표의 값에서의 통행량을 모두 체크해봐야 한다는 것을 알 수 있다.(점에 걸쳐도 인정되므로)

y좌표가 1->3으로 연결되고 통행량이 10,  3->5로 연결되고 통행량이 20이라고 가정해보자.

그러면 1,3,5 모두 들린 y좌표라서 Set자료형에 넣고 iter문을 돌면서 1일때는 +10 3일때는 -10,+20, 5일때는 -20을 해주어서 누적합을 구하는 방식이다.(밑에서 위로 올라가므로 낮은값에 +,높은값에 -를 해주어야 한다.)

또 중요한 것은 무조건 +연산부터 해주어야 한다는 것이다. 점이 걸쳐도 인정되기때문에 위에서 예시로 든 y=3에서 +20으로 연산을 진행해서 최대값을 체크한후 -10을 해주어야한다는 뜻이다.

 

마지막으로 사용된 y좌표들을 정렬하고 중복없이 체크해야할 필요가 있는다. 처음에는  단순하게 Set자료형을 만들고 거기서 또 정렬을 사용했었는데 시간초과가 났다.

코드를 좀 보고 생각을 고쳐 TreeSet을 사용했더니 통과했다.

 

3.코드

4.배운점

• 누적합을 구할 때 정렬된 데이터를 for문 돌면서 시작부분에 +,종료지점에 -를 하는방식을 배웠다.
• TreeSet을 자주 사용할 일이 없어서 생각이 잘 안났다. 정렬도 필요하고 중복도 제거하는 TreeSet 잊지말자