Golang Algorithm - coinChange

문제

다양한 동전들을 가지고 특정 금액을 만들 수 있는 모든 경우의 수를 리턴해야 합니다.

• 예를 들어, 100원, 500원짜리 동전을 가지고 1,000원을 만들 수 있는 방법은 총 3가지 입니다.
• 100원 10개, 100원 5개 + 500원 1개, 500원 2개 
• 위의 경우를 다 합치면 총 3개의 방법이 나옵니다. 더 자세한 것은 입출력 예시를 통해 보시고 그래도 이해가 안된다면 console.log 출력 부분을 보시고 감을 잡으시면 됩니다. 

입력

인자 1 : total

• number 타입의 이하의 자연수

인자 2 : coins

• number 타입을 요소로 갖는 배열
• coins.length는 10,000 이하
• coins[i]는 20 이하의 양의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 동전의 금액은 다양하게 주어집니다.
• coins는 오름차순으로 정렬되어 있습니다.
• 각 동전의 개수는 무수히 많다고 가정합니다.

 

go 풀이 코드

 

go 코드 설명:

1. Go 언어에서 배열을 선언하고 초기값으로 초기화하기 위해서는 make 함수를 사용합니다. 따라서 dp 배열을 make([]int, total+1)로 생성하였습니다.
2. dp[0] 값을 1로 초기화합니다.
3. for 문에서 range 키워드를 사용하여 coins 배열을 순회합니다.
4. 내부 for 문에서 total까지 반복하며, dp[i] 값을 현재 동전으로 만들 수 있는 경우의 수를 누적하여 계산합니다.
5. 모든 동전과 모든 금액에 대해서 계산을 마치면, dp[total] 값은 주어진 동전으로 주어진 금액을 만드는 경우의 수를 담고 있습니다.
6. 이 값을 반환하여 함수를 완료합니다

package main

import "fmt"

func coinChange(total int, coins []int) int {
	dp := make([]int, total+1) // Create an array of size total+1 with initial value 0
	dp[0] = 1                  // Initialize the first element as 1, since there's one way to make 0 money

	for _, coin := range coins {
		for i := coin; i <= total; i++ {
			dp[i] += dp[i-coin] // Accumulate ways of making current amount using current coin
		}
	}
	return dp[total] // Return the total number of ways to make the given total amount
}

func main() {

	total := 10
	coins := []int{1, 5}
	output := coinChange(total, coins)
	fmt.Println(output)

	total2 := 4
	coins2 := []int{1, 2, 3}
	output2 := coinChange(total2, coins2)
	fmt.Println(output2)

}

 

go 출력로그

 

go run coinChange.go 
3
4