# Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

# This theme

AtCoder Beginner Contest D - Redistribution Difficulty: 830

This theme, dynamic programming

It is a problem of so-called typical dynamic programming.

• Previous article --Qiita *, * [AtCoder Beginner Contest E --Crested Ibis vs Monster](https://atcoder.jp/ In contests / abc153 / tasks / abc153_e) *, you have to take care even if you exceed the target value, but this time it's just fine, so it's a little easier. Ruby

#### `ruby.rb`

``````
s = gets.to_i
dp = Array.new(s.next, 0)
dp[0] = 1
s.times do |i|
next if dp[i].zero?
3.upto(s) do |x|
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
end
end
puts dp[s]
``````

#### `ruby.rb`

``````
if i + x <= s
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else
break
end
``````

This time it's just fine, so add dp only for ʻi + x <= s`. Python

#### `python.py`

``````
from sys import stdin

def main():

s = int(input())
dp = [0] * (s + 1)
dp[0] = 1
for i in range(s):
if dp[i] == 0:
continue
for x in range(3, s + 1):
if i + x <= s:
dp[i + x] += dp[i]
dp[i + x] %= 1000000007
else:
break
print(dp[s])
main()
``````

*** PyPy *** is really fast, isn't it?

Ruby Python PyPy
Code length(Byte) 244 405 405
Execution time(ms) 284 509 70
memory(KB) 14400 9060 64596

# Summary

• Solved ABC 178 D
• Become familiar with Ruby
• Become familiar with Python

Referenced site