다이나믹 프로그래밍2 BOJ 12865 - 평범한 배낭(dp, knapsack) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net - 가방에 넣는 물품의 갯수가 최대 100개여서 dfs로 풀면 넣고 안넣고의 경우의 수가 2^100 이기 때문에 O(N^2)가 아닌 다른 방식으로 풀어야한다. 이런 경우 greedy 방식이나 dp 메모이제이션 방식을 고민해볼 수 있다. 조건에서 가방의 제한무게가 10만이하로 주어졌기 때문에 d[i][j] = max(i번째 물건까지 .. 2021. 8. 19. BOJ 11066 - 파일 합치기(DP) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net - 여러 개의 파일을 1개가 남을 때까지 합쳤을 때의 최소비용을 구하는 문제이다. - 페이지를 합치는 부분문제들의 합을 구해야되므로, overlapping subproblem이 있고, 그 중 최소값을 구해야되므로 optimal substructure에 해당된다. 그래서 DP로 접근할 수 있다. - 탑다운 방식 #include #include using namespace std; #defi.. 2021. 8. 17. 이전 1 다음
