package main

import (
	"fmt"
	"math"
)

// Fungsi untuk menghitung jumlah minimum koin dan banyak kombinasi koin
func minCoinsAndCombinations(amount int, coins []int) (int, int) {
	// Array untuk menyimpan jumlah minimum koin untuk setiap nilai
	minCoins := make([]int, amount+1)
	for i := range minCoins {
		minCoins[i] = math.MaxInt32
	}
	minCoins[0] = 0

	// Array untuk menyimpan jumlah kombinasi untuk setiap nilai
	dp := make([]int, amount+1)
	dp[0] = 1

	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			// Perbarui minCoins untuk nilai saat ini
			if minCoins[i-coin]+1 < minCoins[i] {
				minCoins[i] = minCoins[i-coin] + 1
			}
			// Perbarui jumlah kombinasi untuk nilai saat ini
			dp[i] += dp[i-coin]
		}
	}

	return minCoins[amount], dp[amount]
}

func main() {
	// Nominal yang ingin dibentuk
	amount := 146
	// Pecahan koin yang tersedia
	coins := []int{1, 5, 10, 25, 50, 100}

	// Mendapatkan hasil
	minKoin, kombinasi := minCoinsAndCombinations(amount, coins)

	fmt.Printf("Jumlah minimum koin untuk membentuk %d: %d\n", amount, minKoin)
	fmt.Printf("Banyak kombinasi koin untuk membentuk %d: %d\n", amount, kombinasi)
}