[백준] 방 배정하기 (14697번)

문제

정보 초등학교 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을 출력한다.

예제 입력 1 복사

5 9 12 113

예제 출력 1 복사

1

예제 입력 2 복사

3 6 9 112

예제 출력 2 복사

0

---

solved.ac에 dp로 분류되어 있어서 굳이 dp로 풀었는데, 범위도 작고 그냥 계산을 해도 되는 문제이다.

가능한 A,B,C의 모든 조합으로 값을 구해서 가능한지 불가능한지만 조사하자.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%B0%A9%20%EB%B0%B0%EC%A0%95%ED%95%98%EA%B8%B0%20(14697%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;
int A, B, C, N;
int dp[301][301][301];

bool isPossible() {
	for (int i = 0; i < 301; i++) {
		dp[i][0][0] = i * A;
		if (dp[i][0][0] > N) break;

		for (int j = 0; j < 301; j++) {
			if (j != 0) dp[i][j][0] = dp[i][j - 1][0] + B;
			if (dp[i][j][0] > N) break;

			for (int k = 0; k < 301; k++) {
				if (k != 0) dp[i][j][k] = dp[i][j][k - 1] + C;
				if (dp[i][j][k] == N) return true;
				else if (dp[i][j][k] > N) break;
			}
		}
	}
	return false;

	/* 
	for (int i = 0; i < 301; i++) {
		for (int j = 0; j < 301; j++) {
			for (int k = 0; k < 301; k++) {
				int num = i * A + j * B + k * C;
				if (num == N) return true;
				else if (num > N) break;
			}
		}
	}
	return false;
	*/
}

int main()
{
	cin >> A >> B >> C >> N;
	if (isPossible())
		cout << 1;
	else
		cout << 0;

}