2916번 자와 각도기

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

dp 동적 계획 복습 필수 코테 추천 다이나믹 cache 캐시

처음에 백트래킹으로 풀다가 시간 초과나서 캐시로 풀었다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Mod 360
 
int n, k, cnt;
bool cache[366];
vector<int> v;
 
bool chk(int sum, int input)
{
    if ((sum % Mod) == input) {
        return true;
    }
 
    if (cache[sum % Mod]) return false;
    cache[sum % Mod] = true;
 
    for (auto i : v) {
        if (chk(sum + i, input)) {
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &n, &k);
 
    v.assign(n, 0);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
 
    int input;
    for (int i = 0; i < k; i++) {
        memset(cache, false, sizeof(cache));
        scanf("%d", &input);
        if (chk(0, input)) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
 
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define Mod 360
 
int n, k, cnt;
 
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &n, &k);
 
    int G = 360, input;
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        G = gcd(G, input);
    }
 
    for (int i = 0; i < k; i++) {
        scanf("%d", &input);
        printf("%s\n", input % G == 0 ? "YES" : "NO");
    }
 
    return 0;
}