[2017-10-04] Painting the Fence

문제 링크 : https://www.acmicpc.net/problem/5858

1차원 선상에서 소가 좌우로 움직이는데 이 때 두 번 이상 방문한 칸의 개수가 몇 개인지 구하는 문제이다. 움직인 총 거리 상한이 10억으로 주어져 있기 때문에, 단순히 움직이는 걸 시뮬레이션하면서 따라가면 시간 초과가 난다.

 왼쪽, 오른쪽으로 이동 방향이 두 가지라 헷갈릴 수 있지만, 왼쪽으로 움직였든 오른쪽으로 움직였든 상관없이 특정 위치를 몇 번 방문했는지만 중요하기 때문에 모두 오른쪽으로 움직인 구간으로 생각하고 구간에 들어갈 때 +1, 나갈 때 -1로 배열을 기록해서 만들어 두면 쉽게 계산할 수 있다. 이 때 값이 바뀌는 양 끝 구간 개수는 최대 2N개 생기고, 이 위치를 저장하고 관리하기 위해 map등의 자료 구조를 써야하기 때문에 시간 복잡도는 O(NlogN)이 된다. 한 번 +1,-1구간을 만들어두면 2N개 위치를 맨 왼쪽부터 순회하면서 값을 누적하고, 합이 2이상인 개수만 세 주면 된다.