A 씨는 어떤 회사 빌딩의 수위로 일하고 있다. 밤 12시가 되면 A씨는 이 빌딩에 켜져 있는 모든 등과 옥상에 있는 전광판을 소등한 후 퇴근한다. 이 빌딩은 각 층에 동일한 개수의 사무실이 일렬로 늘어서 있고, 건물 양편에 엘리베이터가 있다. 왼쪽에 있는 엘리베이터는 올라갈 때만 탈 수 있는 엘리베이터이고, 오른쪽에 있는 엘리베이터는 내려갈 때만 탈 수 있는 엘리베이터이다.
사무실 등은 왼쪽 엘리베이터를 타고 올라가면서 들러 소등할 수도 있고, 오른쪽 엘리베이터를 타고 내려오면서 소등할 수도 있다. A씨는 왼쪽 엘리베이터 1층에서 출발하여, 소등하기 위해 이동해야 하는 거리를 줄이고 있다. 소등을 시작하기 전에 소등되지 않은 사무실의 정보를 알 수 있으므로, 소등 경로를 최적화하고 싶다. 각 사무실간의 거리는 1이고 층간 이동거리도 1로 가정한다.
Analysis
올해 대회의 최대 쟁점이 되었던 [?] 문제입니다. (제가 생각하는) 주최측의 의도는 왼쪽 엘리베이터를 타고 (중간에 끄면서) 올라간 다음, 오른쪽 엘리베이터를 타고 (중간에 끄면서) 내려오는 경우만 생각한 것 같습니다. 실제로 이렇게 푼 사람들이 대부분 쉽게 해결하고 넘어갔으니까요.
하지만 일부 데이터에서는 위의 방법보다 좋은 답이 존재합니다. 4층짜리 건물에 한 층에 방이 10개 있는 건물이 있다고 합시다. 이 방법에서는 최적해가 2층까지 엘리베이터를 타고 가서, 오른쪽으로 가면서 끄고, 1층으로 내려와서 왼쪽으로 가면서 끄고, 4층으로... 3층으로... 옥상을 지나 내려온다. 가 답이 됩니다. 즉 "왼쪽에 있는 엘리베이터는 올라갈 때만 탈 수 있는 엘리베이터이고, 오른쪽에 있는 엘리베이터는 내려갈 때만 탈 수 있는 엘리베이터이다." 를 서로 다르게 해석한 것이 되지요.
여튼 각각에 대한 풀이를 써 보겠습니다. 우선 올라갔다가 옥상을 지나 내려오는 경우는, 각 층에 대해서 greedy한 방법을 사용하면 됩니다. 우선 2차원 문제를 1차원으로 바꿔서 생각해봅시다. 단층 건물이 있고, 2층에 전광판이 있는 경우이지요. 그러면 1층에서 오른쪽으로 가면서 몇 개의 불을 끄고, 다시 돌아와서 엘리베이터를 타고 2층으로 갑니다. 그 후 오른쪽 엘리베이터를 타고 내려와서 남은 불을 끄지요. 불이 켜져 있는 방 번호를 r1, r2, ..., rn 이라고 한다면 (r1 < r2 < ... < rn) 올라갈때는 r_i 번까지 끄고, 내려갈때는 오른쪽에서 r_i+1번까지 꺼야 합니다. 그러면 이 때의 총 이동거리는, 2 * r_i + n + 2 * (n - r_i+1) = 3 * n - 2 * (r_i+1 - r_i) 가 되지요. 즉 r_i+1 와 r_i의 차이가 가장 큰 지점을 i 로 잡아주면 됩니다. 이 방법을 '각 층에 대해서' 해 줄 수 있지요. 방이 하나도 없는 경우는 그냥 패스, 하나 있는 경우는 양쪽 엘리베이터까지의 거리가 짧은 쪽에서 왕복하면 되고요.
두번째 문제[?]의 풀이는 밥먹고 와서 쓰겠습니다 'ㅅ'/
사실 두번째 문제는 DP (or Back-Tracking) 으로 해결 가능합니다. 반대편 끝까지 가는 층을 몇 개 정해두고, 나머지는 위에서와 같은 그리디로 도는 것이 최적이기 때문이지요. 만약 1,3,4,5층을 반대편 끝까지 간다고 정했다면, 3,5 층은 오른쪽 끝까지, 1,4층은 왼쪽 끝까지 와야 하는거지요. 순서는 3->1->5->4 가 될테고요. 즉 2n개의 층에 대해서 반대편 끝까지 간다고 정했으면, 홀수번째에서는 오른쪽끝->왼쪽끝, 짝수번째에선 왼쪽끝->오른쪽끝 이 됩니다.
astein
Problem Statement
A 씨는 어떤 회사 빌딩의 수위로 일하고 있다. 밤 12시가 되면 A씨는 이 빌딩에 켜져 있는 모든 등과 옥상에 있는 전광판을 소등한 후 퇴근한다. 이 빌딩은 각 층에 동일한 개수의 사무실이 일렬로 늘어서 있고, 건물 양편에 엘리베이터가 있다. 왼쪽에 있는 엘리베이터는 올라갈 때만 탈 수 있는 엘리베이터이고, 오른쪽에 있는 엘리베이터는 내려갈 때만 탈 수 있는 엘리베이터이다.
사무실 등은 왼쪽 엘리베이터를 타고 올라가면서 들러 소등할 수도 있고, 오른쪽 엘리베이터를 타고 내려오면서 소등할 수도 있다. A씨는 왼쪽 엘리베이터 1층에서 출발하여, 소등하기 위해 이동해야 하는 거리를 줄이고 있다. 소등을 시작하기 전에 소등되지 않은 사무실의 정보를 알 수 있으므로, 소등 경로를 최적화하고 싶다. 각 사무실간의 거리는 1이고 층간 이동거리도 1로 가정한다.
Analysis
올해 대회의 최대 쟁점이 되었던 [?] 문제입니다. (제가 생각하는) 주최측의 의도는 왼쪽 엘리베이터를 타고 (중간에 끄면서) 올라간 다음, 오른쪽 엘리베이터를 타고 (중간에 끄면서) 내려오는 경우만 생각한 것 같습니다. 실제로 이렇게 푼 사람들이 대부분 쉽게 해결하고 넘어갔으니까요.
하지만 일부 데이터에서는 위의 방법보다 좋은 답이 존재합니다. 4층짜리 건물에 한 층에 방이 10개 있는 건물이 있다고 합시다. 이 방법에서는 최적해가 2층까지 엘리베이터를 타고 가서, 오른쪽으로 가면서 끄고, 1층으로 내려와서 왼쪽으로 가면서 끄고, 4층으로... 3층으로... 옥상을 지나 내려온다. 가 답이 됩니다. 즉 "왼쪽에 있는 엘리베이터는 올라갈 때만 탈 수 있는 엘리베이터이고, 오른쪽에 있는 엘리베이터는 내려갈 때만 탈 수 있는 엘리베이터이다." 를 서로 다르게 해석한 것이 되지요.
여튼 각각에 대한 풀이를 써 보겠습니다. 우선 올라갔다가 옥상을 지나 내려오는 경우는, 각 층에 대해서 greedy한 방법을 사용하면 됩니다. 우선 2차원 문제를 1차원으로 바꿔서 생각해봅시다. 단층 건물이 있고, 2층에 전광판이 있는 경우이지요. 그러면 1층에서 오른쪽으로 가면서 몇 개의 불을 끄고, 다시 돌아와서 엘리베이터를 타고 2층으로 갑니다. 그 후 오른쪽 엘리베이터를 타고 내려와서 남은 불을 끄지요. 불이 켜져 있는 방 번호를 r1, r2, ..., rn 이라고 한다면 (r1 < r2 < ... < rn) 올라갈때는 r_i 번까지 끄고, 내려갈때는 오른쪽에서 r_i+1번까지 꺼야 합니다. 그러면 이 때의 총 이동거리는, 2 * r_i + n + 2 * (n - r_i+1) = 3 * n - 2 * (r_i+1 - r_i) 가 되지요. 즉 r_i+1 와 r_i의 차이가 가장 큰 지점을 i 로 잡아주면 됩니다. 이 방법을 '각 층에 대해서' 해 줄 수 있지요. 방이 하나도 없는 경우는 그냥 패스, 하나 있는 경우는 양쪽 엘리베이터까지의 거리가 짧은 쪽에서 왕복하면 되고요.
두번째 문제[?]의 풀이는 밥먹고 와서 쓰겠습니다 'ㅅ'/
사실 두번째 문제는 DP (or Back-Tracking) 으로 해결 가능합니다. 반대편 끝까지 가는 층을 몇 개 정해두고, 나머지는 위에서와 같은 그리디로 도는 것이 최적이기 때문이지요. 만약 1,3,4,5층을 반대편 끝까지 간다고 정했다면, 3,5 층은 오른쪽 끝까지, 1,4층은 왼쪽 끝까지 와야 하는거지요. 순서는 3->1->5->4 가 될테고요. 즉 2n개의 층에 대해서 반대편 끝까지 간다고 정했으면, 홀수번째에서는 오른쪽끝->왼쪽끝, 짝수번째에선 왼쪽끝->오른쪽끝 이 됩니다.
16년 전