[SCCC] 동전1_2293번

손시연·2022년 6월 12일
0

SCCC

목록 보기
13/18

동전1_2293번

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k, tmp;
    cin >> n >> k;

    //dp[i] = i원을 만들 경우
    //dp[0] = 0원을 만들 경우 = 동전을 선택하지 않는 경우
    int dp[k+1] = {1};

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        for (int j = 0; j <= k-tmp; j++) {
            dp[j+tmp] += dp[j];
        }
    }

    cout << dp[k];

    return 0;
}

풀이노트

output : k원을 만드는 경우의 수

  • 방법 1: 가장 큰 동전의 개수를 0 1 2 ... 늘려가면서 개수 확인
  • 방법 2: dp[10]=dp[1]dp[9]=dp[2]dp[8]=... 식으로 계산
    -> 손으로 풀어보면 중복되는 경우가 다수 발생

dp[i] : i원을 만드는 경우의 수
dp[0] : 아무 동전을 선택하지 않는 경우
dp[0] = 1

1원에 대해서 dp[i] += dp[i-1]
2원에 대해서 dp[i] += dp[i-2]
5원에 대해서 dp[i] += dp[i-5]

output : dp[k]

profile
Server Engineer

0개의 댓글