문제
접근 방법
처음에는 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; }