프로그래머스 도둑질1 [프로그래머스] 도둑질 (C++) DP 동적프로그래밍이런 배치로 되어있는 마을에서 각 집이 보유하고 있는 돈이 배열로 주어짐누군가 이 집들을 털 계획을 하고 있는데, 두집을 연속으로 털지 못함 (!주의! 첫집과 끝집도 함께 털지 못함)최대로 털 수 있는 금액을 반환하는 문제 접근방법dp문제라서 작은 문제로 쪼개서 하면, dp배열에 i번째 인덱스에 저장되는 값은 i번째까지의 금액이다.dp배열의 값을 입력하는 점화식은 아래와 같음dp1[i] = max(dp1[i-1] , dp1[i-2]+money[i]) --> 바로 전 집까지의 최대값(바로 전 집이 포함되어 있을 수 있음) vs 두칸 전 집까지의 최댓값(i바로 전 집은 포함하지 않음) + 현위치의 집 금액 dp배열이 두개 필요한데, 이유는 첫집은 무조건 포함하고 끝집을 포함하지 않는 조건으.. 2024. 11. 29. 이전 1 다음
