문제 링크)
입력
첫 번째 줄에 운동의 개수
이 주어진다.
두 번째 줄에 각 운동에 필요한 무게
이 공백으로 구분되어 주어진다.
출력
가장 효율적으로 원판을 옮겼을 때, 옮긴 원판의 총무게와 옮긴 원판의 총개수를 공백으로 구분하여 출력한다.
풀이 과정
바벨의 삽입과 제거 횟수는 바벨 양쪽에 대해 개별적으로 계수한다. 이 문제의 복잡성을 낮추기 위하여 일단 봉의 무게 20kg을 제거하고 봉의 한 쪽만을 고려하여 주어진 운동별 요구 중량을 계산한다.
(w_i - 20 ) / 2 = i번 운동을 하기 위해 한쪽에 끼워야하는 무게
그리고 가장 적은 원판을 꽂는 경우를 매우 적은 중량에 대해서 고려해보자.
우선 주어진 원판의 단위는 5, 10, 15, 20이다.
만약 봉에 K만큼 무게가 달려있을 때 이 K kg을 구성하는 가장 적은 원판의 개수는 20kg, 15kg, 10kg, 5kg 순으로 가능한 한 많은 개수를 할당할 때 가장 적다.
따라서 단 하나의 운동을 한다고 하면 움직이는 총 무게 및 횟수는 다음과 같이 계산할 수 있다.
총 무게 = K 2 kg
총 횟수 = (K / 20 + K % 20 / 15 + K % 20 % 15 / 10 + K % 20 % 15 % 10 / 5) 2
(넣었다 빼기 때문에 한 원판 당 2번의 횟수로 계산한다.)(봉의 양쪽에 적용해야 하므로)
최종 무게 = 총 무게 2
최종 횟수 = 총 횟수 2
K는 항상 5의 배수 또는 0이므로 횟수를 구하는 식의 마지막 항에서 항상 나누어 떨어진다.
이제 이 경우를 확장 시켜 생각해보면, 모든 운동을 마친 마지막에는 꽂힌 무게를 하나씩 빼면서 위의 식들에 대입하여 정확한 수를 계산할 수 있다.
중요한 점은 운동을 위해 임의의 무게를 추가할 때 이 무게가 몇 kg의 원판 몇 개로 이뤄지는지 미리 계산하지 않는다는 점이다.
왜냐하면 요구하는 무게가 현재 꽂힌 무게보다 가벼워질 경우 원판을 빼야하는데 미리 구체적인 사항을 정의해버리면 가능한 모든 원판 조합을 고려해야만하는 번거로움이 생기기 때문이다. (간단히 말해 뺄 때에만 각 꽂힌 무게의 원판 조합이 어떻게 되는지 계산한다는 의미이다. 설명이 서툴러 죄송하다.)
그리고 봉에 꽂힌 무게를 모두 합산하여 계산하지 않는 이유는 다음과 같다. 예를 들어서 운동별로 필요한 무게를 계산한 결과 다음과 같이 꽂아야 한다고 해보자.
1 : 40kg, 2 : 90 kg, 4 : 140kg
그럼 1번 운동을 하기 위해 20kg원판 2개를 꽂을 것이다.
2번 운동을 하기 위해 20kg 원판 2개와 10kg 원판 1개를 꽂을 것이다.
3번 운동을 하기 위해 20kg 원판 2개와 10kg 원판 1개를 꽂을 것이다.
하지만 알고리즘에선 꽂을 때 원판 조합을 정하기 않기로 했으므로 다음과 같이 무게가 추가될 것이다.
40kg + 50kg + 50kg 이후 총 무게 = 140kg
운동을 마치고 원판을 뽑을때 140 mod 20 = 0 이고, 몫은 7이므로 추가된 각 무게별이 아닌 모든 무게를 합산한 것으로 횟수를 계산하면 (7 * 2 하므로) 14라는 오답이 계산된다. (실제 정답은 16회이다.)
추가된 무게를 순서에 따라서 저장하기 위해 Stack을 사용할 것이며, 필요한 무게가 현재 꽂힌 무게보다 크다면 단순히 필요한 무게를 stack에 push하고, 감경해야 한다면 최신 무게를 pop하여 그 무게와 감경해야하는 무게를 비교한다.
감경할 무게보다 최신 무게가 크다면, 최신 무게에서 감경할 무게를 뺀다.
감경할 무게보다 최신 무게가 작다면, 감경할 무게에서 최신 무게를 빼고 최신 무게는 버린다.
이과정을 더이상 감경하지 않아도 될 때까지 반복하고, 각 반복마다 감소한 원판무게, 빼내야 하는 원판의 최소개수 * 2를 계산한다. 빼내야 하는 원판의 최소 개수는 감소한 무게를 각 원판 단위를 이용해 나눠가며 계산한다.
여기서 2를 곱하는 이유는 앞서 언급한 것처럼 이 원판을 꽂는 행위도 계수해야하는데 마지막 계산 이전에 pop되어 이 원판 정보가 사라지기 때문이다.
그리고 반복의 마지막에 감경하고 남은 무게를 stack에 push한다.
모든 무게에 대하여 반복하고 남은 stack 요소들에 대해 무게와 최소 이동 횟수를 계산한다.
다음은 이를 구현한 파이썬 프로그램이다.
import sys
def solve() :
N = int(sys.stdin.readline())
weights = list(map(lambda x : (x-20) // 2, map(int, sys.stdin.readline().split())))
stack = []
cur_weights = 0
weight_change = 0
disk_moved = 0
get_movements = lambda x : x // 20 * 2 + (x % 20) // 15 * 2 + x % 20 % 15 // 10 * 2 + x % 20 % 15 % 10 //5 * 2
for w in weights :
if not stack or cur_weights < w:
stack.append(w - cur_weights)
cur_weights = w
else :
diff = cur_weights - w
reduction = 0
top = 0
while diff > 0 :
top = stack.pop()
reduction += min(top, diff)
disk_moved += get_movements(min(top, diff))
tmp = top
top -= diff
diff -= tmp
weight_change += (reduction * 2)
cur_weights -= reduction
if top > 0 : stack.append(top)
for s in stack :
weight_change += 2 * s
disk_moved += get_movements(s)
print(weight_change * 2, disk_moved * 2)
solve()회고
필자는 이 문제를 풀 때 15kg원판의 존재를 모르고 있었다. 20kg, 10kg, 5kg으로만 계산하여 반례를 찾지 못해 난감하던 차에 다시 문제를 읽고 해결하였다.
그간 정신이 없어 못 올린 다른 문제들 중에도 이렇게 문제를 제대로 읽지 않아서 헤매이다 뒷통수를 맞은 경우가 한 둘이 아니다.
책 읽는 습관을 들여도 아직도 독서 능력이 많이 부족함을 느낀다.
