알고리즘 온라인 저지/BOJ (34) 썸네일형 리스트형 BOJ 1005번 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 특정 건물의 선행 건물의 제한이 없으며, 후행 건물 또한 제한이 없기 때문에 단순 트리로는 해결이 불가능하다. 그래프를 이용해야 하며 그래프의 노드가 1000개, 간선이 100000개 이므로 완전 탐색을 한번 돌려도 시간은 충분하다. 즉 완전 탐색을 한번 돌면서 각 노드에 소요시간을 저장해 두기만 해도 해결 가능한 정석에 가까운 문제라는 생각이 들었다. 처음에는 단방향 그래프와 너비 우선 탐색을 이용해 구현하였으나, 이후 포스팅을 준비하면서 내 설명 능력에.. BOJ 5638번 수문 5638번: 수문 첫째 줄에 수문의 개수 n이 주어진다. (1 ≤ n ≤ 20) 다음 n개 줄에는 각 수문 Gi의 유량 (m3/hour) Fi와 피해 비용 Ci가 주어진다. 다음 줄에는 테스트 케이스의 수 m (1 ≤ m ≤ 50)이 주어진다. 다음 m개 www.acmicpc.net 각 수문의 유랑과 비용을 이용해, 조합 가능한 유량의 최소비용을 테이블에 저장하여 풀 수 있는 문제였다. 다만 약간의 함정이 2곳에 있었다. 수문의 정보가 다음과 같이 주어진다면, 배출 가능한 유량과 비용의 테이블을 만들 수 있다. 여기서 요구되는 배출 가능 유량이 4000이라면? 첫 번째 함정이라고 느낀 부분이다. 이 부분은 당연히 200 비용으로 처리되어야 하고, 실제 구현을 해보면 간단하게 처리할 수 있다. (cpp 1.. 이전 1 2 3 4 5 다음
