(UVA) Coin Collector - Solution

Link to the problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2231

The solution below used a Greedy approach to solve this problem.

From the first coin, we check if the sum of the value of all the considered coins is less than the value of the next coin. If so, we add the value of the next coin to our sum. In the end, we only need to check how many coins were added to this sum.


import java.io.*;
import java.util.*;

class Main {
    public int[] coins;
    public HashSet<Integer> myCoins;
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = sc.nextInt();
        for (int test = 0; test < numTests; test++) {
            int numCoins = sc.nextInt();
            coins = new int[numCoins];
            for (int i = 0; i < numCoins; i++) {
                coins[i] = sc.nextInt();
            }
          
            int[] dp = new int[numCoins+1];
            int index = 1;
            dp[index] = coins[0];
            for (int i = 1; i < numCoins-1; i++) {
                if (dp[index]+coins[i] < coins[i+1]) {
                    dp[index+1] = dp[index]+coins[i];
                    index++;
                }
            }

            index += 1; // consider the last element in the array coins
            bw.write(index+"\n");
        }
                                             
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}