[BOJ] 자와 각도기

풀이

2916

맞았습니다!!

1988

0

C++14 / 수정

1736

38초 전

 

1. 완전 탐색 

 

2. 주어진 각도로 만들 수 있는 모든 각도를 구해야 한다. 

만들 수 있는 각도 

• 두 각도를 더한 값 
• 360 - 두 각도를 더한 값 
• 두 각도를 뺀 값의 절대값
• 360 - 두 각도를 뺀 값의 절대값

3. 구한 각도는 

• 구한 각도 저장 배열 angleArray
• 이미 구한 각도를 저장 (bool) angle
• queue<int> 

에 각각 저장한다. 

 

4. 큐를 빠져나왔다면 구할 수 있는 모든 각도를 구한 것.

 

5. 이제 현우가 외친 각도가 angle에 있는지 없는지 확인한 후에 그에 맞는 정답을 출력한다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, k, angleArray[360], idx = 0;
bool angle[361];
 
void bfs()
{
    queue<int> q;
 
    for (int i = 0; i < n; i++)
    {
        q.push(angleArray[i]);
    }
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < idx; i++)
        {
            int res = now + angleArray[i];
 
            if (res <= 360)
            {
                if (!angle[res])
                {
                    angle[res] = true;
                    angleArray[idx++] = res;
                    q.push(res);
                }
                if (!angle[360 - res])
                {
                    angle[360 - res] = true;
                    angleArray[idx++] = 360 - res;
                    q.push(360 - res);
                }
            }
 
            res = abs(now - angleArray[i]);
            // cout <<res << '\n';
 
            if (!angle[res])
            {
                angle[res] = true;
                angleArray[idx++] = res;
                q.push(res);
            }
 
            if (!angle[360 - res])
            {
                angle[360 - res] = true;
                angleArray[idx++] = 360 - res;
                q.push(360 - res);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> k;
 
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> angleArray[idx++];
 
        angle[tmp] = true;
    }
 
    bfs();
 
    for (int i = 0; i < k; i++)
    {
        int tmp;
        cin >> tmp;
 
        if (angle[tmp])
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}