BOJ-2916 자와 각도기

필요한 지식

1. 동적계획법
2. 완전탐색

접근

DP[i][j] : i번째 인덱스의 각도까지 사용했을 때 j각도를 사용할수 있는지 여부
ANS[i] : i 각도를 만들수 있는지 여부

• 만들수 있는 각도를 전부 탐색하고 메모이제이션으로 시간을 줄이고 정답을 출력해 준다.
• DP[j]의 식으로 메모이제이션을 하면 탐색하는 경우가 줄어들게되어 정답을 낼 수 없다. 1514 자물쇠와 같은 이유이다.
• 완전탐색을 할 때에 3가지의 경우가 있다.
  • i-1번째 까지 가져온 각도와 i번째 각도를 더하고 다음 각도로 진행하는 경우
  • i-1번쨰 까지 가져온 각도와 i번째 각도를 빼고 다음 각도로 진행하는 경우
  • i-1번쨰 까지 가져온 각도와 i번째 각도를 더하고 현재 각도에 머무는 경우
• 3번째 경우에서 계속 머무르다보면 각도가 계속 더해지다가 0이 되는 경우가 생기고 그때 다음 각도로 진행하면 i번째 각도를 더하지 않고 다음 각도를 더하는 경우까지 처리할 수 있다.

코드(C++)

#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false), cin.tie(),cout.tie();
using namespace std;
int n, m, x;
vector<int> a;
bool dp[13][361];
bool ans[361];

void go(int idx, int radi) {
    ans[radi] = true;
    if (idx == n) return;
    bool &ret = dp[idx][radi];
    if (ret != false) return;
    ret = true;
    go(idx + 1, (radi + a[idx]) % 360);
    go(idx, (radi + a[idx]) % 360);
    go(idx + 1, (radi - a[idx] + 360) % 360);
}

int main() {
    FIO;
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) cin>>a[i];
    go(0, 0);
    for (int i = 0; i < m; i++) {
        cin >> x;
        cout<< (ans[x]?"YES\n":"NO\n");
    }
    return 0;
}

결과