[Golang] 백준 11047번 : 동전 0 - 고랭 알고리즘 문제 풀이

얼마 전부터 Go 언어를 배우기 시작했다.

빠른 시간 내에 고랭의 문법에 익숙해지기 위해서 알고리즘 문제를 푸어볼 예정이다.

파이썬으로 풀었던 문제이지만 다시 풀면서 빠르게 Go를 익혀보자

문제를 풀고나서 다른 사람들의 코드를 보면서 익숙하지 않은 사용법들을 익혀볼 계획이다.

 

동전 0 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	53997	28653	22442	52.533%

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1

6

예제 입력 2

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2

12

소스코드

package main

import "fmt"

func main() {
	var n, k int
	fmt.Scanf("%d %d\n", &n, &k)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d\n", &a[i])
	}

	var cnt int = 0
	for i := n - 1; i >= 0; i-- {
		cnt += k / a[i]
		k %= a[i]
		if k == 0 {
			break
		}
	}
	fmt.Println(cnt)
}

문제 풀이

1. 주어진 동전은 애초에 오름차순으로 주어지므로 정렬할 필요가 없다.
2. 최소의 동전을 사용하기 위해서는 최대한 큰 동전을 많이 사용해야 한다.
3. 가장 큰 동전부터 작은 순서로 순회하며 나누면서 코인 수를 더해나가면 된다.

새로운 문법

반복문을 돌면서 동전의 수를 카운트하는 부분에서 range 키워드를 사용해서 순회할 수 있다는 것을 알게 되었다.

// 이전 소스코드
var cnt int = 0
for i := n - 1; i >= 0; i-- {
  cnt += k / a[i]
  k %= a[i]
  if k == 0 {
	  break
	}
}

// 새롭게 배운 소스코드
import "sort" // 추가해줘야함

sort.Sort(sort.Reverse(sort.IntSlice(a)))
cnt := 0
for _, v := range a {
	cnt += k / v
	k %= v
	if k == 0 {
		break
	}
}

큰 수에서부터 슬라이스를 순회할 것이므로 역순으로 만들어준다.

range를 사용하면 a라는 슬라이스의 인덱스 값과 요소값을 얻을 수 있다.

 

파이썬 문제 풀이

[파이썬] 백준 11047번 : 동전 0 - 알고리즘 문제풀이

[파이썬] 백준 11047번 : 동전 0 - 알고리즘 문제풀이

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 그리디 알고리즘