B. Modulo Sum

출처: Codeforces B. Modulo Sum

Dynamic programming(DP)

SOL)
주어진 시퀀스에서 임의로 고른 숫자를 m으로 나누어 떨어지는가??
완전 탐색의 경우 2^n이 걸린다.
next = rnt + arr[idx+1] // 현재 조합의 합 + 다음 인덱스의 값
dp[next]를 이미 봤다면 더 나아갈 필요가 없다.
하지만 현재 idx가 dp[next]의 값보다 작다면 새로 값을 갱신 후
재귀를 타야한다. (next를 더 앞의 숫자만으로도 만들수 있는 경우이다.)


[-] Collapse

#include<stdio.h>
#include<cstring>
using namespace std;

int dp[1000];
int arr[1000000];
int n, m, val;
bool cal(int rnt, int idx, bool isSel){
    bool check = false;
    if (isSel && idx != -1 && rnt % m == 0)
        return true;
    if (idx + 1 == n) return false;
    int next = (arr[idx + 1] + rnt)%m;
    if (dp[next] == -1 || dp[next] > idx + 1){
        dp[next] = idx + 1;
        check = cal(next, idx + 1, true);

    }
    if (!check)
        check = cal(rnt, idx + 1, isSel);
    return check;
}

int main(){
    //freopen("input.txt", "r", stdin);
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++){
        scanf("%d", &val);
        arr[i] = val%m;
    }

    if (cal(0, -1, false)) printf("YES");
    else printf("NO");
}