Search
Duplicate

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