[알고리즘 문제 풀기] Coins(3067)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder();

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int t = int.Parse(sr.ReadLine());
    while (t > 0)
    {
        int n = int.Parse(sr.ReadLine());
        int[] a = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        int m = int.Parse(sr.ReadLine());
        int[] dp = new int[m + 1];
        dp[0] = 1;
        for(int i = 0; i < n; i++)
        {
            for(int j=a[i];j<=m;j++)
            {
                dp[j] += dp[j - a[i]];
            }
        }
        sb.AppendLine(dp[m].ToString());
        t--;
    }
    sw.WriteLine(sb);
}

3. 정리

• dp[j]는 j원을 만드는 방법의 수를 저장한다.

• dp[0] = 1로 설정하여 기본값을 설정한다.

• 동전의 종류마다 dp[j] += dp[j - a[i]]를 수행하여 j원을 만드는 방법을 누적한다.

• 최종적으로 dp[m]을 출력하여 문제를 해결한다.