백준 2839번: 설탕 배달

❓ 문제

2839번: 설탕 배달

저번에 풀었던 암호코드와 유사하게 다이나믹 프로그래밍으로 풀면 된다.

💡 풀이

• 점화식: B[w] = min(B[w-3], B[w-5]) + 1
  • 무게 w일 때 필요한 봉지의 개수는 무게가 w-3일 때 봉지의 개수와 무게가 w-5일 때 봉지의 개수 중 작은 값에 1을 더한 값이다.
  • 1을 더하는 이유는 봉지를 하나를 더 쓰게 되니까...
• 당연히 메모이제이션으로 이전에 계산한 값을 활용하게 한다. 안 그러면 시간 초과가 난다.
• 5kg과 3kg은 각각의 무게에 해당하는 봉지가 하나씩만 있으면 되니까 답은 1이다. ⇒ 기저 상태
• 무게가 3 미만이 되면 필요한 봉지의 개수를 구할 수 없으므로 답은 -1

⌨️ 전체 코드

package main

import "fmt"

var m = map[int]int{}

func main() {
	N := 0
	fmt.Scan(&N)
	
	// 기저상태
	m[5] = 1
 	m[3] = 1
	
	fmt.Print(calcLeast(N))
}

func calcLeast(weight int) int {
	if value, exists := m[weight]; exists { //이미 계산해둔 값이 있으면 활용
		return value
	} else if weight < 3 { // 무게가 3이하면 -1
		m[weight] = -1
	} else { // 그 외의 상황에는 w-5, w-3일 때를 재귀호출해 최소값 선택
		m[weight] = min(calcLeast(weight-5), calcLeast(weight-3)) 
	}

	return m[weight]
}

func min(a, b int) int { 
	if a == -1 && b == -1 { // 두 값 모두 -1일 땐 -1 반환
		return -1
	} else if a == -1 { // 두 값 중 하나만 -1일 땐 다른 값에 +1을 반환
		return b + 1
	} else if b == -1 {
		return a + 1
	} else if a <= b { // 두 값 모두 유효하면 작은 값 선택 후 +1
		return a + 1 
	}
	return b +1 
}

🔁 삽질

❌

📖 새롭게 배운 내용

❌

💫 헷갈리는 부분

❌

📚 참고 자료

❌