-
BOJ 1005 [ACM Craft]알고리즘 풀이/DP(동적계획법) 2021. 3. 10. 22:19
BOJ ACM Craft : www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
우선 주어진대로 그림을 그려보니, 그래프가 나왔다.
어떻게 이어볼까,, 고민하다가 역으로 이어보니 답이 나왔다.
페이지에 있는 테스트케이스를 토대로 그려본다.
입력 :
5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4
대략 이런그림이 나온다.
내가 필요한 것은 4에 도달하기까지의 시간이다.
먼저 목표인 4부터, 무엇을 개발해야 하는지 따져본다.
1, 2, 3을 다 개발하면 4를 개발할 수 있는데, 그러면 그때까지의 최대시간은 얼마인가?를 생각해보면
점화식을 구할 수 있다.
dp[4] = max(dp[1], dp[2], dp[3]) + arr[4]
식을 도출한 뒤, 재귀를 이용해 dp[1], dp[2], dp[3]도 똑같은 방식으로 구할 수 있다.
값이 나온 목적지는 배열에 저장해 두고, 나중에 다시 호출되면 써먹는다.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <iostream>#include <vector>#include <algorithm>using namespace std;int values[1001];int N, K;int mem[1001];vector<int> v[1001];int recur(int dest){if (mem[dest] != -1){return mem[dest];}int result = 0;for (int i = 0; i < v[dest].size(); i++){result = max(result, recur(v[dest][i]) + values[dest]);}if (v[dest].size() == 0){result = values[dest];}mem[dest] = result;return result;}int main(){cin.tie(0);ios::sync_with_stdio(0);int t;cin >> t;for (int test_case = 0; test_case < t; test_case++){cin >> N >> K;fill_n(mem, N+1, -1);for (int i = 0; i <= N; i++){v[i].clear();}for (int i = 1; i <= N; i++){cin >> values[i];}for (int i = 0; i < K; i++){int pre, post;cin >> pre >> post;v[post].push_back(pre);}int dest;cin >> dest;cout << recur(dest) << endl;}return 0;}cs 반응형'알고리즘 풀이 > DP(동적계획법)' 카테고리의 다른 글
BOJ 11726 [2xn 타일링] (0) 2018.09.25 BOJ 1463 [1로 만들기] (0) 2018.09.25