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

백준의 방 배정하기(14697) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

세 종류의 방에 학생들을 빈 침대없이 방을 배정할 수 있는지 구해야 하는 문제이다.

먼저, 첫 번째 방에 존재하는 침대의 갯수를 'A개', 두 번째 방에 존재하는 침대의 갯수를 'B개', 세 번째 방에 존재하는 침대의 갯수를 'C개' 라고 가정해보자.

즉, 첫 번째 방은 A인실, 두 번째 방은 B인실, 세 번째 방은 C인실 이라고 표현한 것이다.

이 때, 예약할 첫 번째 방의 갯수를 a개, 예약할 두 번째 방의 갯수를 b개, 예약할 세 번째 방의 갯수를 c개라고 가정해보자.

그럼 이 때, 들어갈 수 있는 학생의 총 수는 A *a + B * b + C * c 명이 될 것이다.

여기서 'A', 'B', 'C'는 입력으로 주어지는 고정된 값이고, 'a' , 'b' , 'c'는 우리가 구해야 하는 값이다.

즉, A * a + B * b + C * c = N 을 만족하는 (a , b , c) 가 존재하는지를 구하면 된다.

이 과정을 본인은 3중 for문을 통해서 나타내 주었다.

A, B, C의 최댓값이 50이기 때문에, N^3이 걸린다고 하더라도, 제한시간내에 충분히 풀이가 가능하다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
using namespace std;
 
int A, B, C, N;
 
void Input()
{
    cin >> A >> B >> C >> N;
}
 
void Solution()
{
    for (int i = 0; i <= N; i++)
    {
        int Student_A = A * i;
        for (int j = 0; j <= N; j++)
        {
            int Student_B = B * j;
            for (int k = 0; k <= N; k++)
            {
                int Student_C = C * k;
                if (Student_A + Student_B + Student_C == N)
                {
                    cout << 1 << endl;
                    return;
                }
            }
        }
    }
    cout << 0 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}