알고 있는 각들로 원하는 각을 만들 수 있는지 구하는 문제입니다.
여러가지 풀이법이 있는 것 같습니다.
확장 유클리드 호제법을 사용하는 방법이 있다고 하는데 저는 잘 몰라서… 다음에 공부를 해야겠습니다.
일단 각 하나를 알고 있으면 그 각의 배수들은 구할 수 있습니다.
예를 들어 60을 알고 있다면 0,60,120,180,240,300은 각도를 구할 수 있습니다.
이 각도들과 다른 각도들을 더하고 뺀 각도들도 구할 수 있습니다.
chk배열에 가능한 각도들을 저장하여 알고있는 각을 입력받고 여태까지 구한 각도들과 더하고 빼며 구할 수 있는 모든 각을 구합니다.
그 후에 원하는 각도를 구할 수 있으면 YES, 없다면 NO를 출력하면 됩니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
FIO;
int n, k;
cin >> n >> k;
bool chk[360] = {};
chk[0] = 1;
FOR(i, 1, n) {
int x; cin >> x;
for (int j = 0;;) {
chk[j] = 1;
FOR(m, 0, 359)
if(chk[m]) chk[(j + m) % 360] = chk[abs(j - m)] = 1;
j = (j + x) % 360;
if (!j) break;
}
}
while (k--) {
int x; cin >> x;
cout << (chk[x] ? "YES\n" : "NO\n");
}
return 0;
}