n일 동안 날마다 과자를 먹는다.
i번째 날에는 과자를 정확히 dᵢ개 먹어야 하고, 그날 가게에서는 과자를 한 개에 pᵢ원에 원하는 만큼 판다.
과자를 사는 날에는 가게에 다녀와야 해서, 몇 개를 사든 그날 차비 f원이 한 번 든다.
과자를 하나도 사지 않는 날에는 가게에 가지 않으니 차비가 들지 않는다.
과자는 그날 먹을 수도 있고, 냉장고에 넣어 두었다가 다음 날 이후에 먹을 수도 있다.
하루는 사기, 먹기, 냉장고에 넣기 순서로 지나간다.
그날 먹고 남은 과자는 모두 그날 밤 냉장고에 넣어야 하고, 냉장고에는 많아야 C개가 들어간다.
냉장고에 넣어 둔 과자는 밤마다 한 개에 h원씩 보관비가 든다.
첫날 아침에는 과자가 하나도 없다.
마지막 날 밤에도 남은 과자가 있으면 냉장고에 넣고 보관비를 낸다.
n일 동안 정해진 만큼 다 먹으면서 쓰는 돈(과자값, 차비, 보관비의 합)의 가장 작은 값을 출력하라.
입력
첫 줄에 n, C, h, f, 둘째 줄에 p₁ … pₙ, 셋째 줄에 d₁ … dₙ이 빈칸으로 나뉘어 주어진다. 1 ≤ n ≤ 500, 0 ≤ C ≤ 500, 0 ≤ h ≤ 1,000,000, 0 ≤ f ≤ 1,000,000,000, 1 ≤ pᵢ ≤ 1,000,000, 0 ≤ dᵢ ≤ 1,000
출력
가장 적은 돈 하나
예시 1 · stdin
4 3 1 8
2 9 9 3
2 2 2 1
stdout
49
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
상태는 '그날 밤 냉장고에 남긴 개수 s'(0 ~ C)예요: best[s] = 그렇게 되기까지 든 가장 적은 돈. 아침에 s개가 있고 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d − s이고, 길은 둘이에요. 가게에 가지 않으면 b = 0이라 s는 s2 + d 하나뿐이고(s2 + d ≤ C일 때만) 돈은 best[s2 + d] + s2·h예요. 가게에 가면min(best[s] − s·p) + (s2 + d)·p + f + s2·h이고 min은 s ≤ s2 + d인 s에 대해서예요(s = s2 + d면 사지도 않고 차비를 낸 셈인데, 앞의 길보다 늘 비싸니 섞여도 괜찮아요). s를 하나하나 다 보면 하루에 C² = 25만 번, 500일이면 1억 2,500만 번이라 Python·크레이콘에는 너무 느려요. s2를 0부터 늘리면 볼 수 있는 s의 범위도 늘어나기만 하니, 앞에서부터 최솟값을 쌓아 가며(low) 하루를 C번에 끝내요. 답은 best[0]이에요 — 마지막 날 밤에 남기면 돈만 더 들어요. 예시: 첫날 2원에 5개를 사서(10 + 차비 8) 2개 먹고 3개(냉장고 가득)를 넣고(3), 둘째 날은 가게에 가지 않고 2개 먹고 1개를 넣고(1), 셋째 날 9원에 2개를 사서(18 + 8) 2개 먹고 1개를 넣고(1), 넷째 날은 가게에 가지 않아요 — 49원이에요. 넷째 날 값이 3원으로 싸지만, 차비 8원을 아끼려고 셋째 날 9원에 하나를 더 사요. 함정 하나: 차비를 잊으면 26원이 나와요 — 차비 없이 냉장고 한도와 보관비만 있는 흔한 풀이로는 안 돼요. 함정 둘: 거꾸로 날마다 차비를 내면(과자를 사지 않는 날도) 틀려요 — 가게에 가지 않는 길을 따로 봐야 해요. 함정 셋: 냉장고 없이 그날그날 사거나, '지금까지 가장 싼 값 + 보관비'로 늘 사는 욕심쟁이는 냉장고 한도와 차비를 따지지 못해서 틀려요 — 어느 날 몫을 미리 살지 골라야 해서 DP가 필요해요. 함정 넷: 보관비를 빼먹거나, 한도를 먹기 전에 재면(s2 + d ≤ C) 틀려요 — 그날 먹을 과자는 냉장고에 넣지 않아요. 함정 다섯: 돈은 차비 500 × 10억 + 과자값 500 × 1,000 × 100만 + 보관비 500 × 500 × 100만 ≈ 1.25×10^12까지 가서 32비트 int(약 21억)를 넘어요. C·C++ long long, Java·C# long이 필요하고, Python 정수는 끝이 없고, JavaScript·TypeScript·크레이콘의 수는 배정밀도 실수라 2^53(약 9×10^15)까지 정확해서 그대로 돼요. '아직 될 수 없음'을 나타내는 값도 언어마다 달라요: Python float("inf"), JavaScript·TypeScript Infinity(Infinity − 수도 Infinity), Java·C#·C·C++는 더하고 빼도 넘치지 않을 큰 수(Long.MAX_VALUE / 4 같은)를 쓰고 비교로 걸러요 — MAX_VALUE 그대로 더하면 넘쳐서 음수가 돼요. 크레이콘은 무한대가 없어서 -1을 '될 수 없음'으로 두고, 최솟값이 아직 없다는 뜻으로는 빈값을 써요(빈값으로 계산하면 멈추니 low == 빈값 || …처럼 먼저 물어요).
Pythonmain.py · 31 줄
import sysdata = sys.stdin.read().split()n, cap, keep, fare = int(data[0]), int(data[1]), int(data[2]), int(data[3])price = [int(x) for x in data[4 : 4 + n]]eat = [int(x) for x in data[4 + n : 4 + 2 * n]]INF = float("inf")# best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈best = [0] + [INF] * capfor day in range(n): p, d = price[day], eat[day] # 오늘 아침 s개가 있고, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s # 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep # 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d) # 그래서 s <= s2 + d인 s 가운데 (best[s] - s * p)가 가장 작은 것만 알면 된다: s2를 늘리며 앞에서부터 최솟값을 쌓는다 new = [INF] * (cap + 1) low = INF # s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 s = 0 for s2 in range(cap + 1): while s <= cap and s <= s2 + d: if best[s] != INF: low = min(low, best[s] - s * p) s += 1 if low != INF: new[s2] = low + (s2 + d) * p + fare + s2 * keep if s2 + d <= cap: # 가게에 가지 않는 날: 차비가 없다 new[s2] = min(new[s2], best[s2 + d] + s2 * keep) best = new# 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다print(best[0])
JavaScriptmain.js · 30 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, cap, keep, fare] = data;const price = data.slice(4, 4 + n);const eat = data.slice(4 + n, 4 + 2 * n);// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 number로 정확하다)let best = new Array(cap + 1).fill(Infinity);best[0] = 0;for (let day = 0; day < n; day++) { const p = price[day], d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 const next = new Array(cap + 1).fill(Infinity); let low = Infinity; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 let s = 0; for (let s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { low = Math.min(low, best[s] - s * p); // Infinity - 수 = Infinity라 따로 거르지 않아도 된다 s++; } next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다console.log(best[0]);
TypeScriptmain.ts · 32 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, cap, keep, fare] = data;const price: number[] = data.slice(4, 4 + n);const eat: number[] = data.slice(4 + n, 4 + 2 * n);// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 number로 정확하다)let best: number[] = new Array<number>(cap + 1).fill(Infinity);best[0] = 0;for (let day = 0; day < n; day++) { const p = price[day], d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 const next: number[] = new Array<number>(cap + 1).fill(Infinity); let low = Infinity; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 let s = 0; for (let s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { low = Math.min(low, best[s] - s * p); // Infinity - 수 = Infinity라 따로 거르지 않아도 된다 s++; } next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다console.log(best[0]);
JavaMain.java · 51 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int cap = Integer.parseInt(st.nextToken()); long keep = Long.parseLong(st.nextToken()); long fare = Long.parseLong(st.nextToken()); long[] price = new long[n]; int[] eat = new int[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) price[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) eat[i] = Integer.parseInt(st.nextToken()); final long INF = Long.MAX_VALUE / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long) long[] best = new long[cap + 1]; Arrays.fill(best, INF); best[0] = 0; for (int day = 0; day < n; day++) { long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 long[] next = new long[cap + 1]; long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = Math.min(low, best[s] - s * p); s++; } next[s2] = low == INF ? INF : low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next; } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 System.out.println(best[0]); }}
C#Main.cs · 48 줄
using System;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int cap = int.Parse(first[1]); long keep = long.Parse(first[2]); long fare = long.Parse(first[3]); long[] price = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); int[] eat = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); const long INF = long.MaxValue / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long) var best = new long[cap + 1]; Array.Fill(best, INF); best[0] = 0; for (int day = 0; day < n; day++) { long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 var next = new long[cap + 1]; long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = Math.Min(low, best[s] - s * p); s++; } next[s2] = low == INF ? INF : low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) // 가게에 가지 않는 날: 차비가 없다 { next[s2] = Math.Min(next[s2], best[s2 + d] + s2 * keep); } } best = next; } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 Console.WriteLine(best[0]); }}
C++main.cpp · 45 줄
#include <algorithm>#include <iostream>#include <limits>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, cap; long long keep, fare; std::cin >> n >> cap >> keep >> fare; std::vector<long long> price(n); std::vector<int> eat(n); for (auto& p : price) std::cin >> p; for (auto& d : eat) std::cin >> d; const long long INF = std::numeric_limits<long long>::max() / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long long) std::vector<long long> best(cap + 1, INF); best[0] = 0; for (int day = 0; day < n; day++) { long long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 std::vector<long long> next(cap + 1, INF); long long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = std::min(low, best[s] - s * p); s++; } if (low < INF) next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = std::min(next[s2], best[s2 + d] + s2 * keep); } } best = std::move(next); } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 std::cout << best[0] << '\n'; return 0;}
Cmain.c · 45 줄
#include <stdio.h>#include <string.h>#define MAXN 500#define MAXC 500#define INF 1000000000000000000LL /* 더하거나 빼도 넘치지 않을 만큼 큰 수 */static long long price[MAXN];static int eat[MAXN];/* best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long long) */static long long best[MAXC + 1], next[MAXC + 1];int main(void) { int n, cap; long long keep, fare; if (scanf("%d %d %lld %lld", &n, &cap, &keep, &fare) != 4) return 0; for (int i = 0; i < n; i++) scanf("%lld", &price[i]); for (int i = 0; i < n; i++) scanf("%d", &eat[i]); for (int s = 0; s <= cap; s++) best[s] = INF; best[0] = 0; for (int day = 0; day < n; day++) { long long p = price[day]; int d = eat[day]; /* 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 */ long long low = INF; /* s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 */ int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF && best[s] - s * p < low) low = best[s] - s * p; s++; } next[s2] = low < INF ? low + (s2 + d) * p + fare + s2 * keep : INF; if (s2 + d <= cap && best[s2 + d] < INF && best[s2 + d] + s2 * keep < next[s2]) { next[s2] = best[s2 + d] + s2 * keep; /* 가게에 가지 않는 날: 차비가 없다 */ } } memcpy(best, next, sizeof(long long) * (cap + 1)); } /* 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 */ printf("%lld\n", best[0]); return 0;}
Craykonmain.cray · 45 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];cap = 첫줄[1];keep = 첫줄[2];fare = 첫줄[3];price = 콘솔.수들읽기();eat = 콘솔.수들읽기();// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(-1은 아직 그렇게 될 수 없음)best = 새목록(cap + 1, -1);best[0] = 0;반복 (day = 0; day < n; day++){ p = price[day]; d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 next = 새목록(cap + 1, -1); low = 빈값; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값(빈값은 아직 없음) s = 0; 반복 (s2 = 0; s2 <= cap; s2++) { 동안 (s <= cap && s <= s2 + d) { 만약 (best[s] != -1 && (low == 빈값 || best[s] - s * p < low)) { low = best[s] - s * p; } s++; } 만약 (low != 빈값) { next[s2] = low + (s2 + d) * p + fare + s2 * keep; } // 가게에 가지 않는 날: 차비가 없다 만약 (s2 + d <= cap && best[s2 + d] != -1 && (next[s2] == -1 || best[s2 + d] + s2 * keep < next[s2])) { next[s2] = best[s2 + d] + s2 * keep; } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다콘솔.쓰기(best[0]);