발상자체는 쉽다고 생각이 들 수 있지만 막상 보면 전혀 쉽지 않은 끔찍한 문제였다.
문제를 읽고 처음 든 생각은 "어? 되게 쉽네?? 이게 왜 다이아지?" 하는 생각이었지만.. 다이아는 다이아다.
이 문제를 풀고 얻은 교훈은 다이아는 그 이유가 다 있기 마련임을 알게 되었다.
먼저 로봇의 이동방식을 보자.
1. 로봇은 앞으로 이동하거나 뒤로 이동한다.
2. 로봇은 벽 위에 놓여있는 센서를 하나 또는 여러 개를 들고 이동할 수 있다.
이 두 가지 조건을 가지고 로봇의 전체적인 이동 과정을 그려보면 아래와 같음을 알 수 있다.
그렇다. 로봇을 최소한의 이동거리로 모든 센서를 배치하려면 어쩔 수 없이 위 그림과 같이 이동해야 한다.
1. 왼쪽구간에 센서가 식별하지 못하는 구역이 있으면 로봇은 센서를 가지러 이동한 후 다시 뒤로 이동해 센서를 배치한다.
모든 센서에 대해 1번 동작을 적용하면 될까?
그렇지 않다. (센서를 뒤로 들고 이동한 거리)*2 만큼 이동 거리가 늘어난다.
그러면 간격이 좁게 배치되어 있는 센서들은 동시에 들고 이동하는 것이 효율적일 수도 있다는 것이다.
이제 문제를 위한 준비과정이 끝났다!!
우선 왼쪽끝부터 오른쪽으로 이동할 때 센서들이 식별할 수 있는 구간을 안전구역이라고 하자.
문제를 풀기 위해 상황을 두 가지로 나눠볼 필요가 있다.
1. 센서를 뒤로 가져와야 하는 경우
여기서 센서의 식별 범위가 안전 구역과 떨어져 있다면 센서의 식별 범위의 끝과 안전구역의 끝과 딱 일치하게 끌어오는 것이 최소한의 이동 경로가 될 것이다.
2. 센서의 식별 범위와 안전구역이 겹치는 경우
이번에 봐야하는 것은 확보된 안전구역과 센서의 식별범위가 겹칠 때이다. 식별범위가 겹친다는 것은 이동해야 하는 경로로 계속 이동해야 하므로 심각하게 받아들일 필요가 없다. 겹친 구간만큼의 식별 범위를 저장하고 다음 센서를 보았을 때 1번과 같은 상황이 존재한다면 1에서 요구하는 이동량에 포함된다. 따라서 센서가 가지는 식별 범위 2*r만큼의 구간을 계속 저장한 채로 1의 상황이 나올 때 갱신한다.
이제 위 두가지 경우를 조합해서 조금 더 구체적으로 상황을 나눌 수 있다.
1을 잘 보면 모든 센서를 왼쪽으로 가져와야 할 때, 따로따로 배치하면 처음에 말했던 것과 같이 이동에 손실이 발생한다. 한 번에 여러 개를 들고 이동하는 게 이득인 상황을 고려해주어야 한다.
여기서 2는 1의 과정에 포함되는 발상으로 볼 수 있다. 하지만 가장 끝 센서가 2의 상황이면 1의 과정이 없으므로 갱신이 될 수 없다. 이는 따로 고려해 최대 장벽 길이 L과 딱 맞게 배치하는 방법을 사용한다.
당연하게도 모든 센서를 어떻게 배치해도 불가능한 경우는 2*r*n<l인 경우이다.
그렇게 이 과정을 거쳐 문제를 풀었고..
눈알을 없앤다는 마인드로 열심히 보았고 그 결과 해결할 수 있었다..
휴.. 한 3번만 더 틀렸으면 진짜 던졌을 것 같다 ㅎㅎ
정말 어려운 문제였고 다시는 보고 싶지 않은 유형의 문제였다.
'BOJ' 카테고리의 다른 글
| BOJ 30108 - 교육적인 트리 문제 (0) | 2024.04.26 |
|---|---|
| BOJ 13306 - 트리 (0) | 2024.04.18 |
| BOJ 17433 - 신비로운 수 (0) | 2024.01.27 |
| BOJ 1437 - 수 분해 (0) | 2024.01.23 |
| BOJ 2014 - 소수의 곱 (1) | 2024.01.23 |