이번에 풀어본 문제는
백준 9084번 동전 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int [] coins = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                coins[i] = Integer.parseInt(st.nextToken());
            }
            int M = Integer.parseInt(br.readLine());
            int [] dp = new int[M + 1];
            dp[0] = 1;
            for (int coin : coins) {
                for (int i = coin; i <= M; i++) {
                    dp[i] += dp[i - coin];
                }
            }

            sb.append(dp[M]).append("\n");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.print(sb);
    }
}

📝 풀이

주어진 동전으로 M원을 만들 수 있는 경우의 수를 출력하는 문제입니다.
dp[0]을 1로 초기화 하고, 동전 값부터 목푯값 M까지 반복문을 수행합니다.
오름차순으로 정렬된 배열이 주어지므로, 동전을 하나 사용하고 남는 값인 dp[i-coin]을 누적하여 더해준다면 결과적으로 모든 경우의 수가 dp 배열에 누적될 수 있을 것입니다.