[백준][DP] 2839. 설탕 배달

2839. 설탕 배달

 

 

• 내 풀이
  • dp[i] = i kg을 만들 때 필요한 최소 봉지 수.
  • 기본값: dp[3] = 1, dp[5] = 1
  • 점화식 구현 방식
    • i-3, i-5 둘 다 불가능(=0) → dp[i]도 불가능(=0)
    • 두 값이 다 가능하면 → dp[i] = min(dp[i-3], dp[i-5]) + 1
    • 한쪽만 가능하면 → 그쪽 값 + 1
  • 즉, 불가능한 값(0)은 min 비교에 넣으면 안 됨.

n = int(input())
dp = [0 for _ in range(max(6, n+1))]
dp[3] = 1
dp[5] = 1
for i in range(6, n+1):
    if dp[i-3] == 0 and dp[i-5] == 0:
        continue
    if dp[i-3] != 0 and dp[i-5] != 0:
        dp[i] = min(dp[i-3], dp[i-5])+1
        continue
    if dp[i-3] == 0:
        dp[i] = dp[i-5]+1
    elif dp[i-5] == 0:
        dp[i] = dp[i-3]+1

print(dp[n] if dp[n] != 0 else -1)

 

 

• 다른 사람 풀이
  • 5로 나뉘는게 무조건 최소 봉지
  • 5로 안되면 모두 3kg 봉지라는 가정하에 sugar-=3, bag+=1

sugar = int(input())

bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  # 5의 배수이면
        bag += (sugar // 5)  # 5로 나눈 몫을 구해야 정수가 됨
        print(bag)
        break
    sugar -= 3  
    bag += 1  # 5의 배수가 될 때까지 설탕-3, 봉지+1
else :
    print(-1)