[백준 2916] 자와 각도기, C++

https://www.acmicpc.net/problem/2916

2916번: 자와 각도기

본 문제는 주어진 n개의 각을 이용해 합하거나 빼서 새로운 각을 만든다. 또한 새로운 각을 이용해서 또 다른 새로운 각을 만드는 것도 가능하다. 주어진 k개의 각을 만들 수 있으면 YES, 없으면 NO를 출력하는 문제다. 문제의 자세한 설명은 링크를 참고하길 바란다.

#include <cstdio>
#include <vector>
 
using namespace std;
 
bool chk[730];
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    // 1. 주어진 n개의 각도로 만들수 있는 모든 각도 만들기
    vector<int> v(n);
 
    // 1.을 통해 만들어진 각도 중 u가 있는지 확인
    vector<int> u(m);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        chk[v[i]] = true;
    }
 
    for (int i = 0; i < m; i++) {
        scanf("%d", &u[i]);
    }
 
    // 두 각을 더하여 새로운 각 만들기
    while (true) {
        bool flag = false;
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v.size(); j++) {
                int tmp = v[i]+v[j];
 
                // 모든 각도는 360보다 작다.
                // 따라서 400도 일 경우 40도로 변경해야 한다.
                if (tmp >= 360) tmp -= 360;
                if (!chk[tmp]) {
                    flag = true;
                    chk[tmp] = true;
 
                    // 새로운 각을 추가
                    v.push_back(tmp);
                }
            }
        }
        if (!flag) break;
    }
 
    // 두 각을 빼서 새로운 각 만들기
    while (true) {
        bool flag = false;
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v.size(); j++) {
                int tmp = v[i]-v[j];
 
                // 음의 각은 양의 각으로 변경한다.
                if (tmp < 0) tmp = -tmp;
                
                // 두 각도의 합이 360을 넘는 경우가 없기 때문에
                // 두 각도의 차가 360을 넘을 수 없다.
                // if (tmp >= 360) tmp -= 360;
 
                if (!chk[tmp]) {
                    flag = true;
                    chk[tmp] = true;
 
                    // 새로운 각을 추가
                    v.push_back(tmp);
                }
            }
        }
        if (!flag) break;
    }
 
    for (int i = 0; i < m; i++) {
        if (!chk[u[i]]) printf("NO\n");
        else printf("YES\n");
    }
}