BOJ)2916 자와 각도기

문제:icpc.me/2916

만들 수 있는 각도들이 주어질 때 그 각도들을 더하거나 빼서 만들 수 있는 모든 각도를 구하는 문제이다.

다이나믹 프로그래밍을 통하여 dp[pos][val] = pos번째 각도 까지 이용하여 구할 수 있는 val(각도)로 구해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, k;
int a[11], dp[361][11], q[11], r[361];
void func(int val, int pos) {
    if (pos == n)return;
    if (dp[val][pos])return;
    dp[val][pos] = true;
    r[val] = true;
    int next = (val + a[pos] + 360) % 360;
    if (!dp[next][pos])func(next, pos);
    next = (360 + val - a[pos]) % 360;
    if (!dp[next][pos])func(next, pos);
    func(val, pos + 1);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < k; i++)
        scanf("%d", &q[i]);
    func(0, 0);
    for (int i = 0; i < k; i++)
        printf("%s\n", r[q[i]] ? "YES" : "NO");
    return 0;
}