백준 2293번 동전 1

🔒[문제 url]

https://www.acmicpc.net/problem/2293

🔑알고리즘

1원, 2원, 5원짜리 동전이 있고 $j$원을 만들고자 할 경우,
경우의 수는 아래 경우의 수들의 합이 된다.
1. dp[j-1] (j-1원을 만드는 경우의 수) + 1 (1원짜리 동전 추가)
2. dp[j-2] (j-2원을 만드는 경우의 수) + 1 (2원짜리 동전 추가)
3. dp[j-5] (j-5원을 만드는 경우의 수) + 1 (5원짜리 동전 추가)

0원을 만드는 경우는 아무 동전을 합하지 않는 경우 하나이므로,
dp[0] = 1로 초기화하고 $j$를 $k$까지 늘려가며 dp를 채운다.

🐾부분 코드

알고리즘을 이해했다면 코드 설명은 따로 필요없어 생략한다.

🪄전체 코드

#include <iostream>
using namespace std;

int n,k;
int coin[101];
int dp[10'001];

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> coin[i];
}


void SOLVE()
{
    dp[0] = 1;

    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
        	// 모든 동전의 가치는 0원 이상
            if(j - coin[i] >= 0)
                dp[j] += dp[j - coin[i]];
        }
    }

    cout << dp[k];
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

어떤 문제든 one try AC를 받으면 기분이 좋다!!😇