Baekjoon(백준) 25095번 - Weightlifting (Google Codejam 2022 Round 1A problem C)

백준 25095번.
문제 제목 : Weightlifting
백준 25095

2022 구글 코드잼의 Round 1A 에서 C 번 문제로 나왔다.

문제 해석

stack에 각 종류의 무게추를 위에 놓거나 위에서 하나를 덜어내는 것이 하나의 operation 이다. 각각의 ‘exercise’ 가 있고 각 exercise 마다 각 종류의 무게추가 있어야 하는 개수가 정해져 있다. 처음에 stack에 아무것도 없는 상태에서 각 exercise의 상태를 순서대로 만들어내고 다시 아무것도 없는 상태로 되돌리기까지 필요한 총 operation 개수의 minimum을 구하라는 문제이다.

풀이 전략

구현

위의 풀이전략 대로 dynamic programming 과 divide and conquer 를 적용하면 된다. recursive function 을 사용하는 것이 가장 일반적인 구현법이 될 것이다. 중간에 실행시간을 줄이기 위해 memoization을 하면서 이미 있는 값은 그대로 계산에 이용하면 된다.
자세한 솔루션은 github 에 있다.

baekjoon 25095 solution code