백준 3541번 상근타워

문제 설명

엘리베이터의 개수가 m개인 매우 높은 타워에서 하나의 엘리베이터만 정해서 탈 때, n번의 버튼을 눌러서 갈 수 있는 가장 낮은 층을 구하는 문제입니다.

 

문제 풀이

아이디어

엘리베이터가 움직일 수 있는 층

상근 타워는 0층부터 매우 높은 층까지, 지상에만 존재하기 때문에 지하로는 내려갈 수 없다. 그러므로 우선 엘리베이터를 위로 올린다음에 아래로 내려서 최대한 낮은 층에 머물 수 있도록 해줘야합니다.

 

낮은 층을 찾는 방법

엘리베이터를 타고 가장 낮은 층에 도착하는 경우의 수는 다시 로비로 되돌아올 경우입니다.

엘리베이터가 다시 로비로 도착할 수 있는 방법은 엘리베이터를 타고 올라간 층수와 내려올 수 있는 층수가 같을 경우입니다.

-> 최소 공배수

 

풀이

반복 찾기

버튼을 누를 때마다 낮은 층수를 유지하면서 위로가기와 아래가기 버튼을 누르게 되는데, 가장 낮은 층은 로비에 도착하는 경우입니다.

이는 위의 아이디어를 통해 각 버튼으로 움직인 층 수가 최소공배수로 같아졌을 때임을 알았습니다.

 

예) 위로 15층 이동 버튼과 아래 12층 이동 버튼이 있을 경우, 위로 총 60층, 아래로 총 60층 이동했을 경우에 로비에 도착하게 됩니다.

 

위의 예시와 같은 경우 위로 이동 버튼 4번 아래 이동 버튼 5번 총 9번의 버튼을 누를 경우 로비로 돌아오게 됩니다.

그러므로, 가장 낮은 층을 유지하면서 버튼을 누르는 방법은 9번마다 반복되게 됩니다.

 

누른 버튼 수 대비 낮은 층 유지하기

상근타워는 지하로 내려갈 수 없으므로 우선 아래 이동 층 수보다 높이 올라가야합니다.

아래 이동 층수보다 높이 올라갔다면, 아래로 이동한 층이 지하가 되지 않는 이상 계속 내려갈 수 있습니다.

 

이를 반복하여 수행하면 현재 누른 버튼 횟수 대비 가장 낮은 층 수를 유지할 수 있게 됩니다.

 

 

 

해결

이번 문제는 의식의 흐름대로 풀 수 있었습니다.

가장 낮은 층을 유지해야됨 -> 내려갈 수 있는 층수가 확보될 때까지 올라가기

가장 낮은 층으로 이동할 경우 -> 로비로 이동하는 것이 가장 낮은 층이고 이는 각 이동 층 수의 최소공배수이므로, 가장 낮은 층수를 유지하는 방법은 최소공배수로 반복되고 있음을 알 수 있습니다.

 

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

3541번: 상근타워

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/3541.py