競技プログラミングを解こう part3

今回はAtcoderのB問題をやってみました〜

B問題はA問題より難易度が高いです。

下記が問題内容です。

問題文

ABC 洋菓子店では, $1$ 個 $4$ ドルのケーキと $1$ 個 $7$ ドルのドーナツが売られている.
このとき, 合計金額が $N$ ドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

制約

• $N$ は $1$ 以上 $100$ 以下の整数

---

入力

入力は以下の形式で標準入力から与えられる.

$N$

出力

合計が $N$ ドルとなる買い方がある場合 Yes, そうでない場合 No と出力せよ.

---

入力例 1 Copy

Copy

11

出力例 1 Copy

Copy

Yes

ケーキを $1$ 個, ドーナツを $1$ 個買えば合計 $4+7=11$ ドルとなる.

---

入力例 2 Copy

Copy

40

出力例 2 Copy

Copy

Yes

ケーキを $10$ 個買えば $4\times 10=40$ ドルとなる.

---

入力例 3 Copy

Copy

3

出力例 3 Copy

Copy

No

ケーキの値段は $4$ ドル, ドーナツの値段は $7$ ドルと, どちらも $3$ ドルより高いためそのような買い方は存在しない.

atcoder.jp

Aに比べると難しい！！

自分はわからなかったので答えを見ました泣

せっかくなので解説していきます！！

入力

入力は以下の形式で標準入力から与えられる.

$N$

 まずは入力からですね。

N = gets.to_i

 

これで入力した数字がNに入ります。

 

出力が難しいですね、、

制約を確認してみましょう。

制約

• $N$ は $1$ 以上 $100$ 以下の整数

上記の制約なので、ケーキは一個4$なので

4$*25個=100$

最大25個買えますね。

次はドーナツです。

同じように考えると、ドーナツは一個7$なので

7$*14個=98$

最大14個買えます。

問題文に下記の記述があります。

同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

なので

ケーキを0〜25個買ったケース+ドーナツを0~14個買ったケースが、入力したNと等しければ'YES'となります。

全部のパターンを考えれば良いのでeachを使います。

(0..14).each do |d|
　(0..25).each do |c|
　　
　end
end

dはドーナツ、cはケーキです。

これで全部のパターンを考えられます。

あとは入力したNと等しければ'YES'、等しくなければ'No'となるようにします。

(0..14).each do |d|
　(0..25).each do |c|
　　if c*4 + d*7 == N
　　　puts 'Yes'
　　　exit
　　end
　end
end

puts 'No'

ケーキ + ドーナツがN$であればYESと出力します。

exitを入れるのはif文が成立したら、そこでプログラムを終了させるためです。

exitがないとプログラムが続いてしまい、Noも出力されてしまいます。

初めは

if c*4 + d*7 == N
　puts 'Yes'

　exit
else
　puts 'No'

　exit
end

でもよくない？と思ったのですが、この場合はNに4が入力されてもeachなので0から順番にd・cに値が入っていきます。

つまり、 if  c*4 + d*7 == N　が成立しなかった時点でelseにはいってしまいます。

だから下記の記述でなくてはいけません。

(0..14).each do |d|
　(0..25).each do |c|
　　if c*4 + d*7 == N
　　　puts 'Yes'
　　　exit
　　end
　end
end

puts 'No'

なんとなくわかったでしょうか？

B問題もスラスラ解けていけるようになりたいですね〜

最後まで読んでいただき、ありがとうございます。