[Gold V] 동전 2 - 2294

문제 링크

성능 요약

메모리: 11148 KB, 시간: 228 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

접근법

DP(Dynamic Programming)에 대해 공부하고 의도적으로 문제 유형을 맞춰서 푼 문제라 그런지 난이도가 어렵지 않았다.

공부한 내용대로 Ai=[Ai-1+1 || Ai-j+1] 라고 점화식을 두고 푸니 쉽게 풀 수있었다.

** i=(전체가격을 모아놓은 배열의 인덱스), j=(주어진 동전가치 배열의 인덱스)

기본적으로 최솟값을 구하는 문제이다보니 배열에 100000의 큰 수를 채워놓고 시작했다.

내 풀이

const fs = require("fs")
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt"

let [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n")

const [N, K] = n.split(" ").map(Number)

input = input.map(Number)

const arr = new Array(K + 1).fill(100000)
arr[0] = 0
input.map((e) => {
  arr[e] = 1
})
function solution(target) {
  for (let i = 1; i < target + 1; i++) {
    for (let j = 0; j < N; j++) {
      if (input[j] < i) {
        arr[i] = Math.min(arr[i], arr[i - input[j]] + 1)
      }
    }
  }
  if (arr[target] === 100000) return -1
  return arr[target]
}
console.log(solution(K))