Search
Duplicate

동전 1

주차
12주차
문제번호
2293
언어
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

체감 난이도 높았습니다.
중복 사용을 피하는 방법에 대한 고민이 필요했습니다.
이차원 배열을 사용하면 안됐습니다.

기본 아이디어

예를 들어,
가지고 있는 동전이 1,2,5 라고 하고, 6원을 만들 수 있는 경우를 계산한다고 하면
1,1,1,1,1,1
1,1,1,1,2
1,1,2,2
2,2,2
1,5
총 5개의 경우의 수가 나옵니다.
이는 "(1로 만들수 있는 6원의 갯수) + (1, 2로 만들 수 있는 6원의 갯수) + (1,2,5로 만들 수 있는 6원의 갯수)"로 표현이 가능합니다.
1로 6을 만드는 경우의 수
→ 1로 5를 만들수 있는 경우 + 1 (즉 1로 5를 만들 수 있는 경우의 수)이고, 1로 5를 만들 수 있는 경우의 수는 1로 4를 만들 수 있는 경우에 + 1 (즉 1로 4를 만들 수 있는 경우의 수)이고, ...
1, 2로 6을 만드는 경우의 수
→ 1로 4를 만드는 경우 + 2 (즉 1로 4를 만들 수 있는 경우의 수)이고 , 1로 4를 만드는 경우의 수는 1로 2를 만들 수 있는 경우에 + 2 (즉 1로 2를 만들 수 있는 경우의 수)이고, ...

코드 설명

이제 제 코드로 설명드리자면, 제 코드에서 바깥 루프는 기본 아이디어에서 주황색 글자에 해당합니다.

Code

제출 날짜

@3/11/2021

메모리

2176 KB

시간

0 ms
#include <iostream> #include <vector> int n, k; std::vector<bool> coin_val; std::vector<int> dp; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { int tmp; input_faster(); std::cin >> n >> k; coin_val.resize(k + 1); dp.resize(k + 1); for (size_t i = 0 ; i < n ; i++) { std::cin >> tmp; if (tmp <= k) coin_val[tmp] = 1; } } void solve() { for (size_t i = 1 ; i <= k ; i++) { if (coin_val[i]) { dp[i] += 1; for (size_t j = i + 1 ; j <= k ; j++) dp[j] += dp[j - i]; } } } void print_val() { std::cout << dp[k] << std::endl; } int main() { input(); solve(); print_val(); return (0); }
C++
복사