第110回【JavaScript】最安値を達成するには 3、【最安値】最安値を達成するには 4
現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
JavaScript をゼロから勉強してみよう、のコーナー 110 回目です。
110 は、お巡りさんですね。ついこないだ、お巡りさんが訪ねて来ました。近くで事件が起きたらしく、各家庭を回って聞き込みを行っているとのこと。お力になりたいところですが、残念なことになんの情報も持ち合わせていませんでした。
それでは、今日も頑張ってみようと思います。
最安値を達成するには 3 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_apples_ste...八百屋にて、りんご x 個が a 円で、りんご y 個が b 円で売られています。
りんごの買い方を工夫したとき、最終的に n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。
入力される値
n x a y b入力値最終行の末尾に改行が１つ入ります。
期待する出力
りんごを n 個手に入れるために必要な金額の最小値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 1,000
・ 1 ≦ x ≦ 1,000
・ 1 ≦ y ≦ 1,000
・ x < y
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ a < b
入力例
4 2 110 5 200出力例
200前回挑戦した問題の応用編、かな。
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
const [n,x,a,y,b] = lines[0].split(/\s/).map(Number);
const dp = Array(n+y).fill(10000000);
dp[0] = 0;
dp[1] = a;
for (let i = 2; i < n + y; i++) {
if (i >= x) dp[i] = Math.min(dp[i],dp[i-x] + a);
if (i >= y) dp[i] = Math.min(dp[i],dp[i-y] + b);
}
console.log(Math.min(...dp.slice(n)));
});Python
n,x,a,y,b = map(int,input().split())
dp = [10000000] * (n+y)
dp[0] = 0
dp[1] = a
for i in range(2,n+y):
if i >= x:
dp[i] = min(dp[i],dp[i-x] + a)
if i >= y:
dp[i] = min(dp[i],dp[i-y] + b)
print(min(dp[n:]))【最安値】最安値を達成するには 4 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_apples_bos...八百屋にて、りんご x 個が a 円で、りんご y 個が b 円で、りんご z 個が c 円で売られています。
りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。
入力される値
n x a y b z c入力値最終行の末尾に改行が１つ入ります。
期待する出力
りんごを n 個手に入れるために必要な金額の最小値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 1,000
・ 1 ≦ x ≦ 1,000
・ 1 ≦ y ≦ 1,000
・ 1 ≦ z ≦ 1,000
・ x < y < z
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ 1 ≦ c ≦ 10,000
・ a < b < c
入力例
9 2 100 3 125 5 200出力例
375とりあえず、今までの応用で簡単に解けそう。ボリュームディスカウントなんでしょうかねぇ。
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
const [n,x,a,y,b,z,c] = lines[0].split(/\s/).map(Number);
const dp = Array(n+z).fill(10000000);
dp[0] = 0;
dp[1] = a;
for (let i = 2; i < n + z; i++) {
if (i >= x) dp[i] = Math.min(dp[i],dp[i-x] + a);
if (i >= y) dp[i] = Math.min(dp[i],dp[i-y] + b);
if (i >= z) dp[i] = Math.min(dp[i],dp[i-z] + c);
}
console.log(Math.min(...dp.slice(n)));
});Python
n,x,a,y,b,z,c = map(int,input().split())
dp = [10000000] * (n+z)
dp[0] = 0
dp[1] = a
for i in range(2,n+z):
if i >= x:
dp[i] = min(dp[i],dp[i-x] + a)
if i >= y:
dp[i] = min(dp[i],dp[i-y] + b)
if i >= z:
dp[i] = min(dp[i],dp[i-z] + c)
print(min(dp[n:]))最後に
好きな問題なので、かなり楽しんでやってます。今後、JavaScript で書くことがあるんだろうか、という疑問は過ぎりますが。Lambda を Python から JS に書き換えてみるとか・・・。
まぁ、言っているだけで、そんな面倒なことはしないでしょう・・・。趣味でフロント作るのに使うくらいですが、DB から取得したデータの加工とか、もしかしたら必要になるかもしれない。
引き続き、よろしくお願いいたします！
