백준[14697] - 방 배정하기

문제

백준 14697 문제 보기

접근 방법

처음에는 dfs로 문제를 접근하려했다. 하지만 dfs로 문제를 풀 경우 O(3^N)이라는 큰 시간복잡도를 보인다. 이를 해결하기 위해 복잡한 예외 처리 및 메모이제이션을 사용해야할 것 같아 다른 방법을 생각해 보았다. 결과적으로 브루스포스로 접근하면 O(N^3)으로 쉽게 해결할 수 있다.

코드

#include <iostream>

using namespace std;

int A, B, C, st;
int temp1, temp2, temp3;

int main() {

    cin >> A >> B >> C >> st;

    for(int i = 0; i <= 113; i ++) {
        temp1 = A * i;

        for(int j = 0; j <= 113; j ++) {
            temp2 = B * j;

            for(int z = 0; z <= 113; z ++) {
                temp3 = C * z;

                if(temp1 + temp2 + temp3 == st) {
                    cout << 1 << endl;
                    return 0;
                }
            }
        }
    }

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