Search
moon
sun

동전 2

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

Memo

•
"동전 1"과의 차이점은 갯수의 최소값을 구하는 것입니다.
•
갯수의 최대값은 1로 10,000을 만드는 갯수인 10,000 입니다.
•
입력을 오름차순으로 받아야 로직이 정상 동작합니다. (sorting 적용)

나눗셈 연산은 비싸다

•
처음 코드 (4ms)
void solve() { size_t ind; for (size_t i = 0 ; i < n ; i++) { ind = coins[i]; for (size_t j = ind; j <= k ; j++) { if (dp[j - ind] != _MAX) dp[j] = std::min(dp[j], dp[j - ind] + 1); else if (!(j % ind)) dp[j] = j / ind; } } }
C++
복사
•
나머지 연산을 위로 올린 코드 (8ms)
void solve() { size_t ind; for (size_t i = 0 ; i < n ; i++) { ind = coins[i]; for (size_t j = ind; j <= k ; j++) { if (!(j % ind)) dp[j] = j / ind; else if (dp[j - ind] != _MAX) dp[j] = std::min(dp[j], dp[j - ind] + 1); } } }
C++
복사
•
나머지 연산을 없앤 나중 코드 (0ms)
void solve() { size_t ind; for (size_t i = 0 ; i < n ; i++) { ind = coins[i]; dp[ind] = 1; for (size_t j = ind; j <= k ; j++) if (dp[j - ind] + 1 < dp[j]) dp[j] = dp[j - ind] + 1; } }
C++
복사
갯수가 가장 적은 것은, 해당 코인을 가지고 있는 값 자체이기 때문에 먼저
dp[ind] = 1;
로 초기화를 해준 후, 원래 dp에 저장된 값과 비교하여 최소의 값을 찾아갑니다.
따라서 나머지 연산이 필요없게 되므로, 속도는 더 빨라집니다.

Code

제출 날짜

@3/23/2021

메모리

2176 KB

시간

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