[백준 / Rust] 6220번: Making Change

문제

6220번: Making Change

Poor Bessie has taken a job in the convenience store located just over the border in Slobbovia. Slobbovians use different coinages than the USA; their coin values change day-by-day!
 
Help Bessie make optimal change for Slobbovian shoppers. You will need to create C (1 <= C <= 1000) cents of change using N (1 <= N <= 10) coins of various values. All test cases will be solvable using the supplied coins.

If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie would make optimum change (minimal coins) of 93 cents by using 1 x 50, 1 x 25, 1 x 10, 1 x 5, and 3 x 1 coins (a total of 7 coins).
 
How hard could it be? The final two test cases will be challenging.

---

문제 이해하기

 N 종류의 코인을 가지고 C센트를 만드는데 필요한 코인의 최소 개수를 구하는 문제입니다. N과 C의 최댓값이 작아서 완전 탐색으로 풀어도 시간 안에 풀 수 있을 것 같습니다. 그런데 이 문제는 N 종류의 코인 각각이 얼마나 필요한지에 대한 부분 문제로 나누어볼 수 있습니다. 그리고 이전 부분 문제의 결과를 누적하여 다음 부분 문제의 결과와 합치다보면 최종적으로 C센트를 만들기 위해 몇 개의 코인이 필요한지를 구할 수 있습니다. 즉, 다이내믹 프로그래밍을 사용하여 문제를 풀 수 있습니다.

---

코드

use std::cmp::min;
use std::io::{stdin, Write};

fn main() {
    let mut writer = std::io::BufWriter::new(std::io::stdout());
    let mut lines = stdin().lines();

    let (c, n) = {
        let line = split_line_to_numbers(&lines.next().unwrap().unwrap());
        (line[0], line[1])
    }; // 만들어야 하는 금액, 동전의 종류

    // dp[i] = i원을 만들기 위해 필요한 동전의 최소 개수, 최솟값을 구해야 하므로 임의의 큰 값으로 초기화
    let mut dp = vec![987654321; c as usize + 1];

    dp[0] = 0; // 0원을 만들기 위해 필요한 동전의 개수는 0개

    for _ in 1..=n {
        let coin = line_to_number(&lines.next().unwrap().unwrap());

        for i in coin..=c {
            dp[i as usize] = min(dp[i as usize], dp[(i - coin) as usize] + 1); // dp[i] = min(dp[i], dp[i - coin] + 1)
        }
    }

    writeln!(writer, "{}", dp[c as usize]).unwrap();
}

fn split_line_to_numbers(s: &str) -> Vec<i32> {
    s.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn line_to_number(s: &str) -> i32 {
    s.parse().unwrap()
}

시간: 4ms

메모리: 13156KB

분류: 다이내믹 프로그래밍

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!