BOJ 2916, 자와 각도기
ProblemSolving ·이 문제는 수학적요소가 있는 DP문제입니다.
풀이
이 문제는 각도가 나올 수 있는 경우의 수를 고려해주고 메모지에이션하면서 재귀를 돌려주시면 됩니다.
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
int n, m,arr[11],dp[361],ans;
int go(int angle)
{
int &ret = dp[angle];
if (ret != -1) return ret;
ret = 1;
for (int i = 1; i <= n; i++)
{
go((angle + arr[i])%360);
if(angle-arr[i]>=0)
go((angle - arr[i]) % 360);
else
go(abs(angle - arr[i]) % 360);
}
return ret;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
memset(dp, -1, sizeof(dp));
go(0);
for (int i = 1; i <= m; i++)
{
scanf("%d", &ans);
if (dp[ans] == 1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}