반응형
2839
-
백준 2839번 - 설탕 배달 파이썬개발/알고리즘 2025. 3. 28. 13:39
📌 백준 2839번 - 설탕 배달 (DP)✨ 문제 요약당신은 설탕을 정확히 N킬로그램 배달해야 합니다.설탕 봉지는 3kg 또는 5kg 두 종류만 있습니다.가장 적은 봉지 수로 N킬로그램을 배달하려면 몇 개가 필요할까요?만약 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.🧠 문제 해석3kg, 5kg 봉지만 사용 가능조합해서 정확히 N을 만들어야 함최소 봉지 수를 구하는 문제 → 최소값 DP🔧 점화식 설계dp[i] = i킬로그램을 만들기 위한 최소 봉지 수기본 점화식:dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1)i-3에 3kg 하나 추가i-5에 5kg 하나 추가둘 중 최소값 선택초기값:dp[0] = 0 (0kg은 봉지 0개)나머지는 float('inf')로 설정 (..