BOJ 1005 - ACM Craft

https://www.acmicpc.net/problem/1005

문제에서 주어지는 테크트리대로 문제 예제와 비슷하게 그래프를 그려보면 DAG 형태가 된다. 이 문제는 DAG(directed acyclic graph, 사이클이 없는 방향 그래프)에서 가장 긴 경로의 길이를 구하는 문제인데, 다이나믹 프로그래밍으로 풀 수 있다.

T[i] = i 번째 건물이 지어지기 위해 게임시작부터 걸리는 최소 시간이라고 하자. 최소 시간이라고 했지만, 사실 T[i]는 i번째 건물에서 끝나는 가장 긴 경로의 길이이다..

C[i] = i 번째 건물'만'을 짓는데 걸리는 시간이라고 하자. T[i]는 i번째 건물을 짓기 위해 지어야하는 선행 건물 j들의 T[j] + C[i]의 최대값이 된다.

이런 종류의 문제를 반복적 DP로 풀려고 하면, 상태의 의존 관계에 따라 테이블의 계산 순서를 정해줘야 한다. 이 문제의 경우는 그래프를 위상정렬 한 순서대로 테이블을 채워주면 된다. (재귀로 풀면 의존관계를 고려하지 않아도 돼서, 훨씬 속편합니다.)

코드 :
http://ideone.com/tR0Wb1

비슷한 문제 :
https://www.acmicpc.net/problem/1948
http://codeforces.com/problemset/problem/615/B
https://www.acmicpc.net/problem/2631

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

Union-Find, Disjoint Set

상호배타적 집합( 서로소집합 )을 표현할때 쓰는 자료구조. 초기에 모든 노드의 부모노드를 자기자신으로 초기화한다. find연산 어떤 노드가 포함된 집합이 어딘지 알기 위해서는 그 노드 자신이 부모노드인 노드가 나올때가지 노드의 부모노드를 타고 올라간다. 이때 이 노드가 그 집합을 대표하는 노드가 되며 만약 어떤 다른 두 노드를 find연산한 결과가 같다면 그 둘은 같은 집합안에 있다. 나중에 find연산시 드는 시간을 줄이기 위해 path compression을 사용 할 수 있다. (return parent[x] = findSet(parent[x])로 부모노드를 바로 이어준다.) union연산 두 집합을 합치는 연산, 어떤 한 집합을 대표하는 노드의 부모노드를 다른 한쪽의 대표노드로 바꿔주면 된다. 이때 find연산시 지나가는 노드 숫자를 줄이기 위해 rank를 비교하여 그에 따라 어떤 집합이 parent가 될지 정한다. (path compression때문에 정확한 rank를 보존 할 수는 없다.) 관련문제 https://www.acmicpc.net/problem/1717 https://www.acmicpc.net/problem/1197 https://www.acmicpc.net/problem/1976 http://codeforces.com/problemset/problem/500/B void init (){ for(int i=0;i<n;++i) parent[i]=i; } int findSet (int x){ if(x==parent[x]) return x; return parent[x] = findSet(parent[x]); } void unionSet (int a, int b){ a = findset(a); b = findSet(b); if(a==b)return; if(rank[a]>rank[b]) parent[b] = a; else
계속 읽기