문제 https://www.acmicpc.net/problem/10265 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 SCC로 새롭게 구성한 컴포넌트 별로 최대, 최소 인원을 파악해 배낭 문제로 값을 구해야 했던 문제로 굉장히 어려웠다.. 일단 인원 마다 같이 가고 싶은 인원(pick)을 가리키도록 그래프로 표현해보자. 1번 인원이 2번 인원과 가고 싶다면 다음과 같이 표현된다. 관계를 이런식으로 나타냈을 때 예제의 입력인 12 3 2 3 4 5 6 7 4 7 8 8 12..

문제 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 풀이 DP의 유형 중에서도 배낭 문제(Knapsack)의 대표 문제이다. 해당 유형의 문제를 풀기 전에는 배낭 알고리즘을 공부하고 풀어보는 것을 추천한다. 배낭 알고리즘은 여러 물건 중에서 특정한 조건을 만족시키는 조합을 구하는 문제들에 적용이 가능하다. 위의 문제에서 우리는 물건들 중에서 최대 무게를 넘지 않는 가치의 최댓값..