Solution

Memo

  • Rust는 브루트포스(백트래킹)로도 종종 통과되길래 처음에는 그렇게 접근했지만, 이 문제에서는 시간 초과가 발생함. (주석 처리한 부분이 그 코드)
  • 이 문제는 전형적인 0-1 Knapsack 문제다.
  • 핵심 아이디어:
    1. 모든 비용(코스트)에 대해 만들 수 있는 최대 메모리 바이트를 dp로 구함
    2. 이 dp 배열에서 target_bytes 이상을 만족하는 최소 비용을 찾아냄
  • dp[i]는 비용이 i일 때 확보 가능한 최대 메모리를 의미함
  • 최종적으로 dp 배열을 순회하면서 target_bytes 이상 확보되는 지점 중 가장 작은 비용(cost)을 answer로 출력
// Baekjoon - 7579
// https://www.acmicpc.net/problem/7579

use std::cmp::{max, min};
use std::io::{self, Read, Write};

fn main() {
    let mut stdin = io::stdin().lock();
    let mut stdout = io::stdout().lock();
    let mut input = String::new();
    stdin.read_to_string(&mut input).unwrap();
    let mut lines = input.lines();

    let parts: Vec<usize> = lines.next().unwrap()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let (n, target_bytes) = (parts[0], parts[1]);

    let input_bytes: Vec<usize> = lines.next().unwrap()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let input_restarts: Vec<usize> = lines.next().unwrap()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let max_cost: usize = input_restarts.iter().sum();
    let mut dp = vec![0; max_cost + 1];

    for i in 0..n {
        let mem = input_bytes[i];
        let cost = input_restarts[i];

        for j in (cost..=max_cost).rev() {
            dp[j] = max(dp[j], dp[j - cost] + mem);
        }
    }

    let mut answer = usize::MAX;
    for cost in 0..=max_cost {
        if dp[cost] >= target_bytes {
            answer = min(answer, cost);
        }
    }

    write!(stdout, "{}", answer).unwrap();
}

// fn get_minimum_bytes_to_restart(
//     inputs: &[(usize, usize)],
//     target_bytes: usize,
//     tmp: &mut Vec<(usize, usize)>,
//     idx: usize,
// ) -> usize {
//     let (sum_bytes, sum_costs): (usize, usize) = tmp.iter()
//         .fold((0, 0), |(a, b), (x, y)| (a + x, b + y));
//
//     if sum_bytes >= target_bytes {
//         return sum_costs;
//     }
//
//     let mut result = usize::MAX;
//
//     for i in idx..inputs.len() {
//         tmp.push(inputs[i]);
//         result = min(result, get_minimum_bytes_to_restart(inputs, target_bytes, tmp, i + 1));
//         tmp.pop();
//     }
//
//     result
// }

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val firstLine = readLine()!!.split(" ").map { it.toInt() }

    val target = firstLine[1];
    val capa = readLine()!!.split(" ").map { it.toInt() }
    val cost = readLine()!!.split(" ").map { it.toInt() }

    val maxCost = cost.sum();
    val dp = MutableList(maxCost + 1) { 0 }

    for (i in 0 until capa.size) {
        for (j in maxCost downTo cost[i]) {
            dp[j] = max(dp[j], dp[j - cost[i]] + capa[i])
        }
    }

    var answer = Int.MAX_VALUE
    for (cost in 0..maxCost) {
        if (dp[cost] >= target) {
            answer = min(answer, cost)
        }
    }

    println("$answer")
    close()
}