[2916번] 자와 각도기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

[1939번] 중량제한 :: http://www.crocus.co.kr/1117?category=159837 문제와 동일하다.

이 문제에서 고려해야될 상황은 하나의 각이 주어지면 

즉, 40도가 주어지면 0, 40, 80, 120, 160, 200, 240, 280, 320, 360이 모두 된다는 것만 고려하면 된다.

그 외에는 위의 문제와 동일하다.

dp[i][sum] :: i번째일때 sum이 존재하면 true 존재하지 않으면 false.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include <iostream> #include <cstdio> #include <algorithm> #include <memory.h>   using namespace std;   int arr[12]; int dp[12][370]; int ans[370];   int n, m;   void dy(int i, int sum) {     if (i > n || dp[i][sum] != -1)         return;       dp[i][sum] = 1;     ans[sum] = 1;       dy(i, (360 + sum - arr[i]) % 360);     dy(i + 1, sum);     dy(i, (360 + sum + arr[i]) % 360); }   int main() {     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);          sort(arr, arr + n);       memset(dp, -1, sizeof(dp));     dy(0, 0);       for (int i = 0; i < m; i++)     {         int val;         bool chk = false;         scanf("%d", &val);           if (ans[val])             printf("YES\n");         else             printf("NO\n");     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus