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++
복사