牛客-コンピュータの再試験問題-Sum of Factorials
4943 ワード
再帰的に解くだけでいいので、最初は0を考えるのを忘れました!の場合、何度かWAしていました..
def DFS(left, right, tmp_value, target):
if tmp_value == target:
return True
if left >= right or tmp_value > target:
return False
for i in range(left, right):
tmp_value += facs[i]
if DFS(i+1, right, tmp_value, target):
return True
tmp_value -= facs[i]
return False
facs = [1, 1]
for i in range(2, 100):
facs.append(facs[i-1]*i)
if facs[i] > 1000000:
break
while True:
try:
n = int(input().strip())
print('NO' if not DFS(0, len(facs), 0, n) or n == 0 else 'YES')
except:
break