2.24. Helping Deroro Quickly

Consider the previous question, when the total width of the building \(W\) gets larger, writing a solution that works in a short time becomes much harder.

Can you write a solution that can quickly determine whether a shape can be constructed or not?

Sample I/O:

Input:
19
5
3

Output:
YES

Input:
97
12
17

Output:
YES

Input:
97
12
18

Output:
NO

Input:
1000000
3
6

Output:
NO

Show the Answer

# This solution uses is an optimization technique called
# memoization which is NOT in the context of this course.

W = int(input())
A = int(input())
B = int(input())

achievable = {0: True}

for i in range(0, W):
    if(i in achievable):
        achievable[i+A] = True
        achievable[i+B] = True

if W in achievable:
    print("YES")
else:
    print("NO")