URI PROBLEMA 2446 - Troco SOLUÇÃO EM C

URI Online Judge | 2446

Troco

Por OBI - Olimpíada Brasileira de Informática 2013  Brazil

Timelimit: 1

Você está num supermercado e está na fila do caixa para comprar alguns produtos. Assim que você termina de passar as compras pelo caixa, se lembra que tem várias moedas em seu bolso, algumas repetidas, e fica pensando se com elas dá para pagar exatamente o valor das compras (para assim se livrar destas moedas e ficar com os bolsos mais leves). Você consegue pagar o valor exato da conta usando estas moedas?

Entrada

A primeira linha da entrada contém dois números inteiros V (1 ≤ V ≤ 105) e M (1 ≤ M ≤ 103), indicando, respectivamente, o valor final da compra e o número de moedas que você tem em seu bolso. A segunda linha contém M números inteiros que descrevem o valor Mi (1 ≤ Mi ≤ 105)de cada moeda existente em seu bolso.

Saída

Seu programa deve imprimir apenas uma linha, contendo apenas um caractere: S caso seja possível pagar o valor exato da conta usando apenas suas moedas, ou N caso contrário.

#include <stdio.h>

#define TAM 100001

int somas_possiveis[TAM];

int main()

{

    int v_desejado, m, moeda,i,v;

    scanf("%d %d", &v_desejado, &m);

    somas_possiveis[0] = 1;

    for (i = 1; i <= v_desejado; i++) somas_possiveis[i] = 0;

    for (i = 0; i < m; i++)

    {

        scanf("%d", &moeda);

        for (v = v_desejado; v >= moeda; v--)

        {

            if (somas_possiveis[v-moeda]) somas_possiveis[v] = 1;

        }

    }

    if (somas_possiveis[v_desejado] == 1) printf("S\n");

    else printf("N\n");

    return 0;

}