![]()
dp[n][m] : n개의 수를 m개의 구간으로 나눴을 때 구간에 속한 수들의 최댓값 점화식을 세워보도록 하자 n개의 원소를 m개의 그룹으로 나눈다. n번째 원소가 포함이 안되는 경우 dp[n][m] = dp[n-1][m] n번째 원소가 포함되는 경우 dp[n][m] = max(dp[n-2][m-1] + (n번째 원소), dp[n-3][m-1] + (n-1 ~ n번째 원소 합), dp[n-4][m-1] + (n-2 ~ n번째 원소 합), .... , dp[1][m-1] + (3 ~ n번째 원소 합)) 다만 여기서 원소합 계산을 편하게 하기 위해 누적합을 이용한다! import java.io.*; import java.util.*; public class Main { static BufferedReader..
![]()
문제 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net dp 의 냄새는 나지만 어떻게 풀어야될지 몰라서 틀린 문제입니다. dp 는 익숙해지는게 어려운 주제인거 같지만 그래도 공부하면 할수록 보이는거 같습니다. 이 문제의 핵심은 knapsack 0-1 입니다. 해당 개념을 모르신다면 백준 12865를 꼭 풀어보시고 풀이를 확인해보시길 바랍니다. 2023.07.04 - [Algorithm🧩] - 백준 12865 평범한 배낭 (0-1 knapsack) 💡풀이 knapsack 1-0 를 떠올려야하는 이유는 구슬을 쓸 수..
