package main

import (
	"fmt"
	"math"
)

// Fungsi untuk mengecek apakah kembalian bisa dibentuk dengan koin yang ada
func canMakeChange(coins []int, amount int) bool {
	dp := make([]bool, amount+1)
	dp[0] = true

	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			if dp[i-coin] {
				dp[i] = true
			}
		}
	}

	return dp[amount]
}

// Fungsi untuk menghitung jumlah minimum koin yang diperlukan
func minCoins(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0

	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] = min(dp[i], dp[i-coin]+1)
		}
	}

	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}

// Fungsi untuk menghitung jumlah kombinasi koin yang bisa membentuk nilai kembalian
func countWays(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 1

	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] += dp[i-coin]
		}
	}

	return dp[amount]
}

// Fungsi untuk menghitung nilai minimum antara dua integer
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	coins := []int{1, 2, 5, 10}
	amount := 100 - 63 // Kembalian adalah 37

	// a. Apakah nominal kembalian dapat dibentuk dari koin pecahan tersebut?
	canMake := canMakeChange(coins, amount)
	fmt.Printf("a. Apakah nominal kembalian dapat dibentuk: %v\n", canMake)

	// b. Berapa jumlah minimum koin yang dapat Anda kembalikan kepada pembeli?
	minCoin := minCoins(coins, amount)
	fmt.Printf("b. Jumlah minimum koin: %d\n", minCoin)

	// c. Berapa banyak kombinasi koin untuk membentuk nilai kembalian tersebut?
	ways := countWays(coins, amount)
	fmt.Printf("c. Jumlah kombinasi koin: %d\n", ways)
}