[백준] 동전 0

1.  문제

■ URL : https://www.acmicpc.net/problem/11047

 

2. 핵심요약

■ 1번째 Row, 1번째 Col : 동전의 갯수

■ 1번째 Row, 2번째 Col : 주어진 동전 가격의 합으로 만들어야할 합계 가격

■ 2번째 Row 부터 : 각 동전의 가격

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

 

3. 문제풀이 접근

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 최소한의 동전 갯수만 사용하기 위해 동전 단가가 큰 것부터 써야 한다.

■ 몫 연산자와 나머지 연산자 문법을 알고 주어진 합계 가격으로부터 필요한 동전의 갯수(최소값)을 구한다.

    - 파이썬 연산자 문법 : 나눗셈의 몫(//), 나눗셈의 나머지(%)

    - 자바스크립트 연산자 문법 : 나눗셈의 몫(/), 나눗셈의 나머지(%)

 

4. 파이썬 코딩

isTest = True
if isTest:
    f = open("./11047.txt", 'r')
    cnt, target = map(int, f.readline().split(' '))
else:
    cnt, target = map(int, input().split(' '))
 
arr = []
for i in range(1, cnt+1):
    if isTest:
        arr.append(int(f.readline()))
    else:
        arr.append(int(input()))
 
answer = 0
arr.reverse()
for item in arr:
    answer += target // item
    target = target % item
 
    if target == 0:
        break
 
print(answer)
 

 

5. JavaScript 코딩

let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./11047.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let cnt = Number(input[0].split(' ')[0]);       // 동전의 갯수
let target = Number(input[0].split(' ')[1]);    // 목표값
 
arr = [];
for(let i = 1; i < cnt + 1; i++) {
    arr.push(Number(input[i]));
}
 
// 문제에서 동전의 가치는 이미 오름차순으로 주어짐.
answer = 0;
for(let i = arr.length - 1; i >= 0; i--) {
    answer += parseInt(target / arr[i]);
    target = target % arr[i];
 
    if (target === 0) {
        console.log(answer);
        return answer;
    }
}