[알고리즘 문제] 백준14697 - 방 배정하기

www.acmicpc.net/problem/14697

14697번: 방 배정하기

처음에 재귀로 문제를 해결하려다가 그냥 for문을 사용해서 풀었습니다. 그냥 for문을 사용해서 풀면 O(N^3)으로 풀 수 있는데 재귀를 사용하면 O(3^N)시간이 걸리게 됩니다. 따라서 재귀로 풀면 시간초과가 나옵니다.

 

1. 재귀버전(3^N)

#include <iostream>
#include <time.h>

using namespace std;

int A, B, C, N;
int ans = 0;
bool isFind = false;

void search(int sum)
{

    if (sum >= N)
    {
        if (sum == N)
        {
            ans = 1;
            isFind = true;
        }
        return;
    }

    search(sum + A);
    search(sum + B);
    search(sum + C);
}
int main()
{

    cin >> A >> B >> C >> N;

    search(0);

    cout << ans << endl;
    return 0;
}

 

2. for문 버전(N^3)

#include <iostream>

using namespace std;

int main()
{
    int A, B, C, N;
    cin >> A >> B >> C >> N;

    for (int a = 0; a <= 100; a++)
    {
        for (int b = 0; b <= 100; b++)
        {

            for (int c = 0; c <= 100; c++)
            {
                if (((a * A) + (b * B) + (c * C)) == N)
                {
                    cout << 1 << endl;
                    return 0;
                }
            }
        }
    }
    cout << 0 << endl;
    return 0;
}