설탕배달

https://www.acmicpc.net/problem/2839

풀이

• d[i]

    ikg을 담을 수 있는 최소 봉지 수
  

• ex) 6kg

    0 + 6 => 6을 3kg짜리 봉지 2개로 담을 수 있음 => d[6] = 2
  

  ​ 1 + 5 => d[1]== -1 => X
  ​ 2 + 4 => d[2]== -1 => X
  ​ 3 + 3 => d[6] = d[3] + d[3] = 1

• ex) 10kg

    0 + 10 => 10을 5kg짜리 봉지 2개로 담을 수 있음 => d[10] = 2 
  

  ​ 1 + 9 => d[1]== -1 => X
  ​ 2 + 8 => d[2]== -1 => X
  ​ 3 + 7 => d[7]== -1 => X
  ​ 4 + 6 => d[4]== -1 => X
  ​ 5 + 5 => d[5] == 1 => d[10] = d[5] + d[5] = 2

• 위와 같이, 앞 단계에서 사용된 값이 재사용된다. 따라서 DP

• 더 간결하게 어떻게 짤 수 있을까?