백준[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;
}
Share