[백준 14697] 방 배정하기

문제 링크 : https://www.acmicpc.net/problem/14697

14697번: 방 배정하기

 

입력이 1 2 5 50이라고 가정해보자

 

먼저 확실하게 알 수 있는 것은

 

 전체 인원이 1명, 2명, 5명일 때 빈 침대 없이 배정 가능하다는 점이다.

 

그리고 2명일 때 완벽하게 배정이 가능하기 때문에

 

2명에 1명 2명 5명을 더한 3 4 7도 마찬가지로 빈 침대 없이 배정 가능하다.

 

3 4 7 에서 위의 과정을 계속 반복하면, 12, 17 ... 등등 다양한 수에 대해서

 

빈침대 없이 배정 가능한지 알 수 있다.

 

---

 

위의 내용을 반대로 생각해보자

 

만약 7이 빈침대 없이 배정 가능한지 궁금할 때

 

7에서 1, 2, 5를 뺀 6, 5, 2 중 어느 하나라도 빈침대 없이 배정 가능하다면

 

7도 마찬가지로 빈침대 없이 배정 가능할 것이다.

 

(셋다 배정 불가능 하다면 7도 마찬가지로 불가능)

 

---

 

재귀적인 구조를 가진 문제이지만 동적 계획법을 사용하면 반복문으로 $O(n)$에 해결할 수 있다.

 

DP[i]는 총 인원이 i명일 때 빈침없 배분이 가능한지이다.

 

#include <iostream>
using namespace std;

int main(void) {
	int a, b, c, total;
	int dp[301];

	cin >> a >> b >> c;
	cin >> total;
	dp[0] = 1;

	for (int i = 1; i <= total; i++) {
		if (i >= a) {
			if (i >= b) {
				if (i >= c) {
					dp[i] = dp[i - a] + dp[i - b] + dp[i - c];
				}
				else {
					dp[i] = dp[i - a] + dp[i - b];
				}
			}
			else {
				dp[i] = dp[i - a];
			}
		}
		else {
			dp[i] = 0;
		}
	}

	if (dp[total] == 0) {
		printf("0\n");
	}
	else {
		printf("1\n");
	}
}