【AtCoder-Ruby】ABC105 B - Cakes and Donuts

問題

問題文

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

制約

N は 1 以上 100 以下の整数

問題リンク

考えたこと

• DFS（深さ優先探索）

回答

CP = 4
DP = 7

N = gets.strip.to_i

def dfs(c, d, p)
  return c + d if p == 0
  return 0 if p < 0 

  res = 0
  res += dfs(c + 1, d, p - CP)
  res += dfs(c, d + 1, p - DP) if res == 0
  return res
end

res = dfs(0, 0, N)
p res
puts res > 0 ? 'Yes' : 'No'

考察

もっと良い書き方は？（正解者を参照）

他の人の回答を見ていると全探索で解いている。
ループの最大値は、ケーキの料金（4）を合計金額で割ったもの +1 で良さそう。
また、金額の計算は一方の金額と合計金額にて算出

CP = 4
DP = 7

N = gets.strip.to_i

is_exist = false
((N / CP) + 1).times do |i|
  rem = N - (i * CP)
  if rem >= 0
    if (rem % DP) == 0
      is_exist = true
      break
    end
  else
    break
  end
end
puts is_exist ? 'Yes' : 'No'

まずは、全探索を検討するが定石。