목재 조각 분할 최적화
문제 개요
길이가 각각 $ L_i $인 $ n $개의 나무 막대가 연속적으로 연결되어 있습니다. 이 중에서 최대 $ m $개의 접합부를 자를 수 있으며, 자른 후 만들어진 조각들 중 가장 긴 조각의 길이가 최소가 되도록 해야 합니다. 또한, 그러한 조합의 경우의 수를 구하고 결과를 $ 10007 $로 나눈 나머지를 출력해야 합니다.
해법 접근
이 문제는 두 가지 부분으로 나뉩니다: ...
8월 9일 08:44에 게시됨
구간 동적 계획법을 활용한 돌무더기 합치기 문제 분석 및 확장
문제 개요
이 문제는 주어진 돌 무더기들을 인접한 쌍으로 합쳐 나가며, 각 합산 시점에서 두 무더기의 무게 합을 점수로 얻는 최대 점수를 구하는 전형적인 구간 동적 계획법(Interval DP) 모델이다. 기본 버전은 선형 배열 형태이며, 본 문제는 원형 배열을 처리해야 하는 고난도 버전이다.
기본 해법: 선형 배열 처리 (약화된 버전)
각 돌 무더기의 무게가 배열로 주어 ...
6월 23일 22:28에 게시됨