백준 2597 줄자접기 문제 풀이
백준 2597 줄자접기 문제 풀이
백준 온라인 저지, 2597번: 줄자접기
도입
줄자를 접어 만나도록 할 두 점에 대해서, 두 점의 중점을 기준으로 중점의 한 편에 위치한 모든 점을 대칭 이동하여 대응한다.
문제 풀이
편의상 여기서 조금 더 확장하여 다음의 규칙에 따라 처리한다.
- 처리 대상의 두 점의 중점을 구한다.
- 대칭 이동: 항상 중점의 오른쪽에 위치한 모든 점과 줄자의 끝을 중점에 대해 대칭 이동한다.
- 평행 이동: 항상 줄자의 왼쪽 끝 좌표가 0이 되도록 한다. 만약 줄자의 오른쪽 부분이 왼쪽 부분보다 길어서, 음수 좌표 점이 발생한다면, 왼쪽 끝이 0이 되도록 모든 점을 오른쪽으로 평행 이동한다.
항상 왼쪽 끝이 0이 되도록 함으로써, 오른쪽 끝의 좌표가 곧 줄자의 길이가 되도록 한다.
줄자의 왼쪽 끝 좌표를 따로 추적한다면, 평행 이동 과정을 수행할 필요는 없다. 결과를 산출하는 마지막 단계에서 줄자의 양쪽 끝 좌표의 위치 차를 구하는 것으로도 대응할 수 있다.