반응형
1. 문제
■ URL : https://www.acmicpc.net/problem/11047
2. 핵심요약
■ 1번째 Row, 1번째 Col : 동전의 갯수
■ 1번째 Row, 2번째 Col : 주어진 동전 가격의 합으로 만들어야할 합계 가격
■ 2번째 Row 부터 : 각 동전의 가격
|
1
2
3
4
5
6
7
8
9
10
11
|
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
|
cs |
3. 문제풀이 접근
■ 문제유형 : 탐욕(Greedy) 알고리즘
■ 최소한의 동전 갯수만 사용하기 위해 동전 단가가 큰 것부터 써야 한다.
■ 몫 연산자와 나머지 연산자 문법을 알고 주어진 합계 가격으로부터 필요한 동전의 갯수(최소값)을 구한다.
- 파이썬 연산자 문법 : 나눗셈의 몫(//), 나눗셈의 나머지(%)
- 자바스크립트 연산자 문법 : 나눗셈의 몫(/), 나눗셈의 나머지(%)
4. 파이썬 코딩
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
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)
|
cs |
5. JavaScript 코딩
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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;
}
}
|
cs |
반응형
'알고리즘(코딩테스트)' 카테고리의 다른 글
| [백준] 주유소 (0) | 2024.10.05 |
|---|---|
| [백준] 수들의 합 (0) | 2024.10.05 |
| [백준] 설탕 배달 (0) | 2024.10.04 |
| [백준] 읽어버린 괄호 (0) | 2024.10.04 |
| [백준] ATM (1) | 2024.10.03 |
