문제
원리
- dy의 초기배열은 1000으로 높게 해준다. (dy[0]=0)으로 한다.
-> 가장 작은 수를 구해야 하므로 높은 숫자인 1000으로 한다. - 각 칸은 동전 몇개로 위의 숫자를 만들수 있나를 나타낸 것이다.
예) coin[i] = 1일때, 2를 만들려면 2개가 필요하다. - 각 칸의 들어갈 수는 dy[j-coin[i]]+1을 통해서 구해진다.
a. j는 coin[i]의 숫자부터 m까지이다.
b. +1을 해주는 이유는 무조건 coin[i]를 한개는 쓰겠다는 의미이다.
코드
- Javascript
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, coin){
let answer=0;
let dy=Array.from({length:m+1}, ()=>1000);
dy[0]=0;
for(let i=1; i<arr.length; i++){
for(let j=coin[i]; j<=m; j++){
dy[j]=Math.min(dy[j], dy[j-coin[i]]+1);
}
}
answer=dy[m];
return answer;
}
let arr=[1, 2, 5];
console.log(solution(15, arr));
</script>
</body>
</html>- Swift
func solution(m: Int, arr: [[Int]]) -> Int {
var answer = 0
var dy = Array(repeating: 0, count: m+1)
for i in stride(from: 0, through: arr.count-1, by: 1){
var ps = arr[i][0]
var pt = arr[i][1]
for j in stride(from: m,through: pt, by: -1){
dy[j] = max(dy[j], dy[j-pt]+ps)
}
}
answer = dy[m]
return answer
}
var tmp = [[10,5], [25,12], [15,8], [6,3], [7,4]]
print(solution(m: 20, arr: tmp))
Live the way you think