백준 13334번 철로 - 스위프트(Swift) 풀이 + 그림 설명

 전형적인 스위핑 문제이다. 문제에서 보여주는 그림에서 빨간색 철로를 왼쪽부터 오른쪽으로 싹 밀면서 포함되는 사람 수를 훑는다고 생각하면 된다. 이때 0, 1, 2, 3, 4, 5... 이렇게 모든 좌표마다 철로를 멈추면서 탐색할 필요 없이, 집/사무실이 있는 좌표에만 멈춰서 탐색하면 된다. (어차피 집/사무실이 없는 좌표는 카운트 변화가 일어나지 않는 의미 없는 좌표이기 때문에)

철로를 밀 때는 시작점/끝점 둘 중 하나를 기준으로 잡은 뒤, 하나씩 우측으로 이동시켜 나가면서 d를 초과하지 않게 반대점을 선택해서 최대한 길게 철로를 그리면 된다. 나는 끝점을 기준으로 잡고 풀어보았다. 아래는 그림으로 나타낸 과정인데 주황색으로 표시된 것들을 카운트하면서 철로를 밀어야 한다. 따라서 현재 좌표가 몇 번째 사람의 좌표인지를 기억해둬야 한다.

끝점 좌표 1로 시작(사실 철로 건설이 불가능하므로 고려할 필요 없다)

 

끝점 좌표 1 > 4로 이동

 

끝점 좌표 4 > 5로 이동, 시작점은 움직이지 않음(철로 길이 d 이내이므로)

 

끝점 좌표 5 > 9로 이동, 시작점 움직이지 않음(아직도 철로 길이 d 이내)

 

끝점 좌표 9 > 10으로 이동, 시작점도 우측으로 이동(철로 길이가 d이내가 될 때까지)

 

끝점 좌표 10 > 12로 이동, 시작점 그대로

 

 사람들끼리 좌표가 겹칠 수 있다는 조건이 걸릴 수 있는데, 생각해보면 상관이 없다는 것을 알 수 있다. X라는 좌표에 0번 사람의 집, 1번 사람의 사무실, 2번 사람의 집.. 이렇게 여러 개 있다고 하면, 하나만 탐색하는 것이 아니라 각각을 모두 탐색해서 카운트가 점점 늘어나기 때문이다.

반응형