목록직관 (1)
유진정의 기록
🔪 막대 자르기 최소 비용 - 접근법 비교 분석
📌 문제 소개[귀찮음](https://www.acmicpc.net/problem/16208) 문제소개합니다.🔍 문제 분석처음 문제를 봤을 때 몇 가지 관점에서 접근해봤다:총 길이가 정해져 있고 잘라야 하는 길이도 정해져 있다.n개의 막대를 만들려면 n-1번 자르는 연산이 필요하다.자르는 순서에 따라 비용이 달라질 수 있다고 생각했다.🧩 처음 시도한 접근법 DP = 행렬 체인 곱셈 스타일 접근첫 번째로 떠올린 접근법은 동적 계획법(DP)이다. 이 문제가 행렬 체인 곱셈(Matrix Chain Multiplication) 문제처럼 느껴졌기 때문이다. 행렬 체인 곱셈(Matrix Chain Multiplication) 문제는 여러 행렬을 곱할 때 연산 횟수를 최소화하는 괄호 배치를 찾는 문제다. 이 문제..
개인공부/데이터분석&알고리즘
2025. 4. 15. 11:53