Dynamic Programming + Brute Force
문제
정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다.
예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명 이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년 여학생 전체가 112명이라면 빈 침대 없이 방을 배정하는 것은 불가능하다.
방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오. 단, 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.
입력
표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.
출력
빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.
import sys
a, b, c, n = map(int, sys.stdin.readline().split())
dp = [0] * 301
dp[a] = dp[b] = dp[c] = 1 # 기준점들을 1로 할당
for i in range(a, n + 1): # 5명부터의 범위가 시작해야 가장 작은 5짜리 방을 쓸 수 있다.
for j in [a, b, c]:
if i >= j and dp[i - j]:
dp[i] = 1
print(dp[n])기준점은 dp[5], dp[9], dp[12]가 된다. 가령 학생수가 10명일 때 크기 5짜리 방 2개를 주면 된다. 14명일 때는 5짜리 1개, 9짜리 1개로 배정할 수 있다. 따라서 5부터 n까지의 값들을 계산할 때
해당 숫자의 5, 9, 12 전의 값이 1이면 그 숫자는 배정이 가능한 상태이며 이 방식으로 dp 배열을 n까지 확장해나간다. 45명이어도 5 x 9(개), 9 x 5(개) 둘 중 하나에만 해당되면 배정가능하므로 답은 1이 된다.
동전 1(2293)과 비슷한 유형의 문제
