[백준/14697/파이썬] 방 배정하기

https://www.acmicpc.net/problem/14697

14697번: 방 배정하기

Problem

• 방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오

조건

• 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.
• 표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.
• 빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.

SOL

동전문제가 떠오르는 문제이다.

Subtask를 봤을 때, 동전문제와같이 Greedy방법으로 풀려면, B,C는 A의 배수관계가 성립해야한다.

그렇다면, 결국 모든 경우를 다 봐야하는데, 이 문제는 N이 300밖에 되지않기 때문에, N^3까지해도, 거뜬히 문제가 풀린다.

Brute Force로 푼다고했을 때

이 문제는 A//N,B//N,C//N 까지 모든 경우의 수를 다 확인해주면 된다.

A, B, C, N = map(int, input().split())

x = result = 0
for c in range(N // C + 1):
    for b in range(N // B + 1):
        for a in range(N // A + 1):
            x = a * A + b * B + c * C
            if x == N:
                result = 1
print(result)

 

DP로 푼다면, 

DP[N] = N명일 때, 빈 침대가 없도록 방 배정이 가능한 경우

예를들어, A,B,C =[2,3,5] 라고 하고, N= 10이라고 하자.

N=1	2	3	4	5	6	7	8	9	10
0	1 2인실(A)	1 3인실(B)	1 2인실*2 (A+A)	1 2인실 1개 3인실 1개 (A+B)	1 3인실*2 (B+B) or 2인실*3	1 2인실 1개 5인실 1개 (A+C)	1 3인실 1개 5인실 1개 (B+C)	1 2인실*2 5인실 1개 (A+A+B)	1 5인실*2 (C+C) or 2인실*5 (A+A+A+A+A) or 2인실 *2 3인실 *2 (A+B+A+B)

위와 같이 DP table이 형성될거다.

여기서, 알 수 있는 규칙은, DP[x] = 1이라면, DP[x+a],DP[x+b],DP[x+c]는 가능하다는 거다.

예를들어, DP[2] =1이면, DP[2+2],DP[2+3],DP[2+5]는 가능하다. 말로 풀어보면 당연하다. 

왜냐하면, 2인실이 가능하고, 우리가 갈 수 있는게 2인실,3인실,5인실이라면, 당연히 4명,5명,7명을 수용할 수  있다.

즉,DP[x-a],DP[x-b],DP[x-c] 셋 중 하나라도 1이라면 , DP[x] =1이다.

A,B,C,N= map(int,input().split())
DP=[0]*(301)

DP[A]=DP[B]=DP[C] = 1
for i in range(A,N+1):
    for j in [A,B,C]:
    # i>=j (음수가 아닐 때, DP[i-j] =1이라면,DP[i]는 가능한 경우이다)
        if i>=j and DP[i-j]:
            DP[i] =1

print(DP[N])