티스토리 뷰

알고리즘 관련/BOJ

BOJ)2916 자와 각도기

JASON 자손9319 2017. 3. 1. 14:39
문제:icpc.me/2916

만들 수 있는 각도들이 주어질 때 그 각도들을 더하거나 빼서 만들 수 있는 모든 각도를 구하는 문제이다.


다이나믹 프로그래밍을 통하여 dp[pos][val] = pos번째 각도 까지 이용하여 구할 수 있는 val(각도)로 구해주면 된다.


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
#include <cstdio>
#include <algorithm>
using namespace std;
int n, k;
int a[11], dp[361][11], q[11], r[361];
void func(int val, int pos) {
    if (pos == n)return;
    if (dp[val][pos])return;
    dp[val][pos] = true;
    r[val] = true;
    int next = (val + a[pos] + 360) % 360;
    if (!dp[next][pos])func(next, pos);
    next = (360 + val - a[pos]) % 360;
    if (!dp[next][pos])func(next, pos);
    func(val, pos + 1);
}
int main() {
    scanf("%d%d"&n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d"&a[i]);
    for (int i = 0; i < k; i++)
        scanf("%d"&q[i]);
    func(00);
    for (int i = 0; i < k; i++)
        printf("%s\n", r[q[i]] ? "YES" : "NO");
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10816 숫자 카드2  (1) 2017.03.01
BOJ)1890 점프  (0) 2017.03.01
BOJ)2916 자와 각도기  (0) 2017.03.01
BOJ)3049 다각형의 대각선  (0) 2017.03.01
BOJ)9577 토렌트  (0) 2017.02.22
BOJ)5430 AC  (0) 2017.02.21
댓글
댓글쓰기 폼