백준] 14697 - 방 배정하기(KOI 2017 전국 - 초등부, 중등부)

시간 제한 : 2초

메모리 제한 : 512MB

입력

표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.

출력

빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int a, b, c, n, tmp = 0;
	bool arr[351] = { false, };
	cin >> a >> b >> c >> n;

	for (int i = a; i <= n; i += a)
		arr[i] = true;
	for (int i = b; i <= n; i += b)
		arr[i] = true;
	for (int i = c; i <= n; i += c)
		arr[i] = true;

	if (!arr[n])
	{
		for (int i = 1; i <= n; i++)
		{
			if (arr[i])
			{
				for (int la = i + a, lb = i + b, lc = i + c; la <= n;)
				{
					arr[la] = arr[lb] = arr[lc] = true;
					if (la <= n)
						la += a;
					if (lb <= n)
						lb += b;
					if (lc <= n)
						lc += c;
				}
			}
			if (arr[n])
				break;
		}
	}

	if (arr[n])
		cout << 1;
	else
		cout << 0;
}

Tip

동적계획법에서 사용하는 테이블 작성 방법을 응용해서 빈 침대 없이 배정 가능한 숫자들을 다 마킹하는 방식으로 문제를 풀었다. 좀 더 깔끔하게 풀 수 있을 것 같은데, 당장 떠오르는 방법으로 풀어냈다.