백준 14697 - 방 배정하기
Updated:
C++
14697 번 - 방 배정하기
문제
방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오. 문제 출처
접근 방법
문제 형태가 재귀함수를 요구한다고 판단하여 재귀함수로 접근하였다.
하지만 재귀함수로 문제를 해결하기 위해서는 O(3^N)의 시간복잡도를 요구하여 시간 초과라는 결과를 얻는다.
따라서 단순하게 반복문 3개를 통해 O(N^3)의 시간복잡도로 해결하였다.
두번째는 다이나믹 프로그래밍을 통하여 해결하였다.
만약 주어진 방의 크기가 3 5 7라고 생각하자, 그렇다면 사람이 각각 3, 5, 7명 일때 각 방의 크기에 맞게 배정이 된다.
즉 위의 3, 5, 7명에서 3을 먼저 본다. 이 3명에서 각 방의 크기 3, 5, 7를 더한 6, 8, 10명의 사람이 있을 때 빈 침대가 없도록 방 배정이 가능하게 되는 것이다.
이에 따라 배정 가능한 사람의 수를 계속 더하며, 만약 주어진 수가 위 덧셈의 결과에 없는 경우에 0이 되며 이는 빈 침대가 없도록 방 배정이 불가능하다는 것이다.
구현 - Loop
반복문 3개를 통하여 각 방의 사이즈를 하나씩 증가하여 사람의 크기가 맞는지 확인한다.
코드 - Loop
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int roomSize[3], total;
bool result = false;
bool DFS(int a, int b, int c);
void forloop();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < 3; i++) {
cin >> roomSize[i]; //각 방 사이즈 3개 저장
}
cin >> total;
forloop();
cout << result;
}
void forloop() {
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
for (int k = 0; k < 100; k++) {
if ((i * roomSize[0]) + (j * roomSize[1]) + (k * roomSize[2]) == total) { //세 방의 크기의 합이 주어진 사람 수 이면 성공 후 리턴
result = 1;
return;
}
}
}
}
}
//결과는 나오지만, 시간초과가 된다.
bool DFS(int a, int b, int c) {
int sum = (a * roomSize[0]) + (b * roomSize[1]) + (c * roomSize[2]);
if (sum > total) {
return false;
}
else if (sum == total) {
result = 1;
return true;
}
if (DFS(a + 1, b, c))
return true;
if (DFS(a, b + 1, c))
return true;
if (DFS(a, b, c + 1))
return true;
return false;
}
구현 - DP
최대 사람의 수는 300명 이므로, 1부터 300까지의 수를 담을 수 있는 배열을 선언한다.
사람의 수를 1부터 주어진 사람의 수 까지 1씩 더해가며, 해당 사람의 수 일때 빈침없 방 배정이 가능한지 DP로 확인한다.
역으로 생각하면, 현재의 사람의 수가 15명이고 방의 크기가 3, 5, 7이면 / 이 15명에서 3, 5, 7을 뺀 12 - 10 - 8 명의 방 중 하나라도 빈침없이 가능하면 15명의 사람의 수도 빈침없이 가능하다.
따라서 현재 사람의 수에서 방의 크기만큼 빼야 하므로, 현재 사람의 수가 방의 크기보다 작은 경우를 대비하기 위해 조건문으로 확인한다.
코드 - DP
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int roomSize[3], total;
bool result = false;
void dp();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < 3; i++) {
cin >> roomSize[i];
}
cin >> total;
dp();
cout << result;
}
void dp() {
dpNum[0] = 1; //처음 3개의 방 크기에 빈침없 방 배정이 가능하다고 나타내는 수 1
for (int human = 1; human <= total; human++) {
if (human >= roomSize[0]) { //사람의 수가 첫번째 방의 크기보다 클 때
if (human >= roomSize[1]) { //사람의 수가 두번째 방의 크기보다 클 때
if (human >= roomSize[2]) { //사람의 수가 세번째 방의 크기보다 클 때
dpNum[human] = dpNum[human - roomSize[0]] + dpNum[human - roomSize[1]] + dpNum[human - roomSize[2]];
}
else {
dpNum[human] = dpNum[human - roomSize[0]] + dpNum[human - roomSize[1]];
}
}
else {
dpNum[human] = dpNum[human - roomSize[0]];
}
}
}
if (dpNum[total] != 0) //0이 아닐 시에는 앞 선 빈침없 방의 사람의 수에서 더한 것이므로, 빈침없을 만들 수 있다.
result = 1;
}
