[알고리즘] BOJ-14916: 거스름돈

골드 레벨 문제를 풀다가 어려워지면 바로 실버 문제로 리프레시를 해보자. 하하...언젠간 골드 레벨 문제도 바로바로 풀 수 있게될거야!

백준 14916 - 거스름돈(링크)

재귀로 풀면 되나? top to bottom

나는 이 문제를 재귀로 접근하는 풀이법을 직관적으로 떠올렸다.

만약 n이라는 금액을 만들기위해 5짜리 동전을 하나 사용하는 경우, n-5라는 금액을 만들기 위해서 필요한 최소한의 동전 개수를 구하고, n-5라는 금액을 만들기 위해 5짜리 동전을 하나 사용하는 경우, n-5-5라는 금액을 만들기 위해서 필요한 최소한의 동전 개수를 구하고...

이렇게 말이다.

하지만, 이 재귀 풀이의 경우에 발생할 문제점이 한 가지 있다.

중복되는 계산이 많다는 것!

f(n)을 이제부터 n금액을 만들기 위한 최소한의 동전 개수를 구하는 함수라 부르겠다.

금액 15를 만들기 위해 5짜리 동전 하나를 사용하는 경우, f(15) = 1+ f(10)이다.

금액 12를 만들기 위해 2짜리 동전 하나를 사용하는 경우, f(12) = 1 + f(10)이다.

그렇다면 금액 17을 만드는 경우를 생각해보자. f(10)의 계산이 불필요하게 중복이 될 것이다.

그러면 DP로 접근해보자 bottom to top

왜 dp냐고? 재귀는 dp와 조건이 같다.

• 더 작은 부분문제로 문제의 크기를 줄일 수 있다
• 상위 문제가 부분문제의 결과에 영향을 받는다

어떤 값을 저장할 것인가

DP로 접근할 때는, dp 테이블의 인덱스가 의미하는 값과, 해당 인덱스 위치에 저장되는 값의 의미를 마음 속으로 정의해놓고 로직을 생각해야 수월하다. 내가 어떤 데이터를 메모이제이션 해야하지?를 잘 생각해보자.

금액 k를 만들기 위한 최소한의 동전 개수

그렇다. 그러면 dp 테이블의 초기값은 어떠해야 하는가? 아마 매우 큰 수여야 할 것이다. 그래야 최소값을 업데이트하기 수월하니까 말이다.

어떻게 초기화할 것인가

그래서 dp테이블을 최대 정수로 초기화해주었다. 더불어 dp[0]을 0으로 초기화해주었는데, 그 이유는 동전 하나로 한 번에 어떤 금액을 만들 수 있는 경우를 처리하기 위해서이다.

이후 과정은 쉽다.

dp테이블의 인덱스는 내가 만들고자 하는 금액으로 삼고,

• 동전 5와 2를 순회하며 금액에 맞는 최소 동전개수로 dp테이블을 업데이트 시켜준다.

여기까지 생각을 했다면 로직을 작성해보자.

내 예시코드가 없어도 아마 문제를 거뜬히 맞출 수 있을 것이다.

다만, 문제 마지막에 금액을 주어진 동전으로 만들 수 없는 경우, -1을 출력하는 조건에 주의하자! (그렇지 않으면 95%정도에서 틀리게 된다 ㅜㅜ)

아아... 방랑자여, 아쉽지만 정답에 도달하지 못했는가? 그러면 내 변변찮은 예시 코드를 보고 다시 한 번 도전해보시게나.

const N =
  require('fs')
    .readFileSync(process.platform === 'linux' ? 'dev/stdin' : 'test/test.txt')
    .toString()
    .trim() * 1

const dp = Array.from({ length: N + 1 }, () => Number.MAX_SAFE_INTEGER)
dp[0] = 0

for (let target = 1; target <= N; target++) {
  [2, 5].forEach((coin) => {
    if (coin > target) return
    dp[target] = Math.min(dp[target], dp[target - coin] + 1)
  })
}

console.log(dp[N] > N ? -1 : dp[N])

그럼 화이팅이다!