백준 알고리즘 14697번 방 배정하기(python)

간단한 브루트포스 알고리즘 or 다이나믹 프로그래밍 문제이다.

브루트포스 알고리즘 풀이

a, b, c, n = map(int, input().split())
res = 0
for i in range(0, n+1, a):
    for j in range(0, n-i+1, b):
        for k in range(0, n-i-j+1, c):
            if i+j+k == n:
                res = 1
print(res)

다이나믹 프로그래밍 풀이

a, b, c, n = map(int, input().split())
li = [a, b, c]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    for t in li:
        if i-t >= 0 and dp[i-t]:
            dp[i] = 1
print(dp[n])