[Python] ABC011 C

問題

C – 123引き算

回答

全探索は \( 3^{100} \) であり、難しい。

貪欲法

3を引けるときにそれより小さい数字を引く必要はないので、引ける数のうち最も大きな数字を引けば良い。

N = int(input())
NG = [int(input()) for _ in range(3)]

def check(N, NG):
    if N in NG:
        return 'NO'

    num = N
    for _ in range(100):
        if num - 3 not in NG:
            num -= 3
        elif num - 2 not in NG:
            num -= 2
        elif num - 1 not in NG:
            num -= 1
        else:
            return 'NO'
    
    if num > 0:
        return 'NO'
    return 'YES'

print(check(N, NG))

動的計画法

dp[N] を０として、ある数字にたどり着くまでに最低必要な手数をdp[i]として動的計画法を行います。

N = int(input())
NG = [int(input()) for _ in range(3)]

f_inf = float('inf')
dp = [f_inf] * 301
dp[N] = 0

for i in range(N, -1, -1):
    if i in NG:
        continue
    for j in range(1, 4):
        dp[i-j] = min(dp[i]+1, dp[i-j])

if dp[0] <= 100:
    print('YES')
else:
    print('NO')