반응형
SMALL
1516 게임 개발 파이썬
-
백준 1516번 게임 개발, 1700번 멀티탭 스케줄링 (Python)알고리즘 2023. 9. 8. 09:49
1516번 게임 개발 건물을 짓는 속도와 이전에 지어져야하는 건물들이 주어질 경우, 모든 건물을 짓는데 걸리는 시간을 구하는 문제입니다. 전형적으로 Dynamic Programming를 활용해 풀 수 있는 문제라고 생각했습니다. dp에 저장할 값은 각 번호의 건물을 짓는데 걸리는 속도로 했습니다. 우선, 이전에 지어져야하는 건물이 없는 건물의 경우 자신만 지으면 되므로 건물을 짓는데 걸리는 시간을 dp에 저장했습니다. 그 이후 건물을 짓기 전 필요한 건물이 있을 경우 해당 건물들이 지어지는 속도를 우선 확인하도록 했습니다. 건물의 번호를 i라 할 때, dp[i]에 값이 존재한다면 그 값을 반환해주었고, 값이 없다면 해당 건물을 지을 때 필요한 시간을 측정해줍니다. dp[i]의 값은 (필요한 건물들의 건설..