# [Gold II] 금고 열기 [문제 링크](https://www.acmicpc.net/problem/9320) ## 문제 설명 <p>비밀 요원 상근이는 시리아의 화학 무기에 대한 정보를 보관하고 있는 금고를 열려고 한다. 금고를 열려면 금고에 암호를 입력해야 한다. 암호는 숫자 네 개로 이루어져 있다.</p> <p>상근이는 시도해야 하는 암호의 목록을 가지고 있다. 목록에는 매우 많은 암호가 적혀있기 때문에, 암호가 될 수 없는 것을 미리 지우려고 한다.</p> <p>올바른 암호는 24 조건을 만족한다. 암호를 이루는 수 네 개 사이에 덧셈, 뺄셈, 곱셈, 나눗셈, 괄호를 적절히 삽입해서 24를 만들 수 있을 때, 그 암호를 24 조건을 만족한다고 한다.</p> <p>예를 들어, (4, 7, 8, 8)은 (7-8/8)*4 = 24이기 때문에, 24 조건을 만족한다. 하지만, (1, 1, 2, 4)나 (1, 1, 1, 1)과 같은 암호는 24 조건을 만족하지 않는다. 따라서, 이러한 암호는 시도해볼 필요가 없다.</p> <p>가능한 암호가 모두 주어졌을 때, 24 조건을 만족하는지 안 하는지를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다. 각 테스트 케이스는 한 줄로 이루어져 있고, 가능한 암호를 나타내는 네 정수 a, b, c, d (1 ≤ a, b, c, d ≤ 9)가 주어진다.</p> ## 출력 <p>각 테스트 케이스 마다, 입력으로 주어진 암호가 24 조건을 만족하면 "YES"를, 만족하지 않으면 "NO"를 출력한다.</p> ## 풀이 #### 수와 연산자, 괄호를 백트래킹으로 배치하여 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; int arr[4]; bool visited[4]; bool calc(vector<double> vals) { if(vals.size()==1) return 23.99999999<=vals[0] && vals[0]<=24.00000001; bool ret=false; vector<double> next; next = vals; next[1] = next[0] + next[1]; next.erase(next.begin()); ret |= calc(next); next = vals; next[1] = next[0] - next[1]; next.erase(next.begin()); ret |= calc(next); next = vals; next[1] = next[0] * next[1]; next.erase(next.begin()); ret |= calc(next); next = vals; next[1] = next[0] / next[1]; next.erase(next.begin()); ret |= calc(next); next = vals; next[next.size()-2] = next[next.size()-2] + next[next.size()-1]; next.erase(next.end()-1); ret |= calc(next); next = vals; next[next.size()-2] = next[next.size()-2] - next[next.size()-1]; next.erase(next.end()-1); ret |= calc(next); next = vals; next[next.size()-2] = next[next.size()-2] * next[next.size()-1]; next.erase(next.end()-1); ret |= calc(next); next = vals; next[next.size()-2] = next[next.size()-2] / next[next.size()-1]; next.erase(next.end()-1); ret |= calc(next); return ret; } bool back(int depth, vector<double> vals) { if(depth==4) return calc(vals); bool ret=false; vector<double> next; for(int i=0;i<4;i++) { if(!visited[i]) { visited[i]=true; next = vals; next.push_back(arr[i]); ret |= back(depth+1, next); if(depth!=0) { next = vals; next.back() += arr[i]; ret |= back(depth+1, next); next = vals; next.push_back(-arr[i]); ret |= back(depth+1, next); next = vals; next.back() -= arr[i]; ret |= back(depth+1, next); next = vals; next.back() *= arr[i]; ret |= back(depth+1, next); next = vals; next.back() /= arr[i]; ret |= back(depth+1, next); } visited[i]=false; } } return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { for(int i=0;i<4;i++) cin >> arr[i]; cout << (back(0, {}) ? "YES\n" : "NO\n"); } } ```