[백준 / BOJ] 1516 게임 개발

문제

출처 : www.acmicpc.net/problem/1516

1516번: 게임 개발

N개의 건물이 주어지고, 각 건물을 짓는 시간과 그 건물을 짓기위해 먼저 지어야할 건물들이 주어진다.

이때 각 건물을 짓기 위해 필요한 최소 시간을 구하는 문제다.

(각 건물은 동시에 지을수있다.)

 

풀이

N의 최댓값이 500이라 완전탐색을 하게되면, 최악의경우 501^2*250 만큼 돌아서 시간초과가 난다.

 

DP로 풀리는 문제였다.

 

각 건물을 짓기위해 지어야할 선행건물들을 모두 지었다면 건설을 시작할수있다.

이때, 건물은 동시에 지을수있기때문에 (선행건물, 선행에 선행 건물..... 도 해당됨) 선행건물들의 값중 max값을 가져와서 현재 지을려는 건물에 더해주면된다.

 

따라서, dp식은

dp[현재건물] = cost[현재건물] + max(dp[선행건물(1 ~ i-1)]dp[선행건물(2 ~ i)]) 가 된다.

매 순간마다 이렇게 계산하면 시간초과가 나기때문에, 한 건물에 대해 탐색할때 해당 건물의 선행건물들을 전부 업데이트 시켜줘야한다.

(바텀업 방식으로 구현하면됨)

 

1. 입력을 전부 받고 선행건물이 없는 건물들을 모두 짓는다. dp[건물] = cost[건물]

 

2. N번 반복하면서, dp[현재건물]값이 초기값인경우 3번 으로 간다.

 

3-1. 현재건물을 짓기위해 지어야할 선행건물들이 모두 지어진경우 선행건물들의 dp값중 max값을 가져와 현재건물에 더해준다. 

 

3-2. 선행건물들의 dp값중 초기값인 선행건물이 있다면, 선행건물을 인자로 3번을 호출한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1516%20%EA%B2%8C%EC%9E%84%20%EA%B0%9C%EB%B0%9C/main.cpp

devxb/JJUNalgo