728x90 반응형 백준 28391 [백준/Python] 2839 설탕배달 | DP(다이나믹 프로그래밍) 📒 문제 🤸♀️ 문제 분석 다른 블로그를 보면 반복문(while)로 구현하여 greedy 방법으로 푼 풀이가 많은데, 요즘 DP 연습을 하고 있기 때문에 DP로 접근하여 문제를 풀었다. DP 테이블에는 '각 무게 별 사용하는 봉지의 최소값'을 저장한다. 이것을 가능하게 하는 조건은 아래와 같다. 3키로와 5키로 각각의 설탕봉지가 있기 때문에, 3키로 전 / 5키로 전 dp값에서 작은 값에 +1 한 값을 현재 dp에 할당하면 된다. 💡 경우의 수는 아래와 같이 세 가지 경우가 있다. case 1) 3kg전, 5kg전의 봉지사용 최소값이 둘 다 존재하는 경우(봉지로 옮길 수 있는 경우), 두 값에 +1 한 것 중 작은 값을 현재 dp에 할당한다. case 2) 3kg전 혹은 5kg 전 둘 중 하나만 존재하.. 2022. 3. 31. 이전 1 다음 728x90 반응형