코드포스 알고리즘 최적화: 동적 계획법, 그리디, 서로소 집합을 활용한 문제 풀이
1787C - Remove the Bracket
동적 계획법(DP)을 사용하여 괄호를 제거했을 때의 최소 비용을 계산하는 문제입니다. 각 원소를 특정 임계값 $k$를 기준으로 두 부분으로 나누고, 이전 상태의 최소값을 갱신하는 방식으로 접근합니다. 상태 전이 시 곱셈 연산이 발생하므로, 각 위치에서 0번과 1번 선택지에 따른 누적 비용을 독립적으로 관리하여 최적해를 도출합니다.
#inc ...
6월 5일 21:57에 게시됨