๐ฃ ๋ฌธ์ ์ดํด
1. n๊ฐ์ง ์ข ๋ฅ์ ๋์ ์ด ์ฃผ์ด์ง๋ค.
2. ์ด ๋์ ๋ค์ ์ฌ์ฉํด์, ๊ทธ ๊ฐ์น์ ํฉ์ด k์์ด ๋์ผํ๋ค.
3. ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ต์์ ๋์ ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ค๊ณ ํ๋ค. ๊ฐ๊ฐ์ ๋์ ์ ๋ช ๊ฐ๋ผ๋ ์ฌ์ฉํ ์ ์๋ค.
4. ์ฌ์ฉํ ๋์ ์ ๊ตฌ์ฑ์ด ๊ฐ์๋ฐ, ์์๋ง ๋ค๋ฅธ ๊ฒ์ ๊ฐ์ ๊ฒฝ์ฐ์ด๋ค.
๋์ ๊ณํ๋ฒ(Dynamic Programming) ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ญ ํ์ด ๊ณผ์
<coinArr>
1 | 5 | 12 |
coinArr์ ๋์ ๊ฐ์น๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด ์ด๋ค.
์ฃผ์ด์ง ๋์ ์ข ๋ฅ๋ 1, 5, 12 ์ธ ๊ฐ์ง ์ด๋ค.
์ด๋ std::sort ํจ์๋ฅผ ์ฌ์ฉํด์ ๋์ ์ข ๋ฅ๋ฅผ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํด๋๋ค.
<dp>
0 | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ | ์ด๊ธฐ๊ฐ |
dp ๋ ์ธ๋ฑ์ค๊ฐ ๊ฐ์ด๊ณ ๊ทธ ๊ฐ์ ์ฑ์ธ ์ ์๋ ์ต์ ๋์ ๊ฐ์๋ก ์ฑ์์ง๋ ๋ฐฐ์ด ์ด๋ค.
dp[0] ์ 0 ์ผ๋ก ์ด๊ธฐํํ๊ณ , ๋๋จธ์ง๋ 987654321(์ด๊ธฐ๊ฐ) ์ด๋ผ๋ ๊ฐ์ผ๋ก ์ด๊ธฐํ ํจ์ผ๋ก, ๊ทธ ์ธ๋ฑ์ค์ ํด๋นํ๋ ๊ฐ์ด ๊ฐ์ง ๋์ ์ผ๋ก ๋ง๋ค ์ ์๋ ๊ฐ์ธ์ง๋ฅผ ํ์ธํ ์ ์๋ค.
(๋ถ๊ฐ๋ฅํ ๊ฐ์ด๋ผ๋ฉด 987654321 ์ด ๊ทธ๋๋ก ๋จ์์๊ฒ ๋๋ค.)
์ฒซ ๋ฒ์งธ ๋์ ๊ฐ์น์ธ 1์ ๊ฒฝ์ฐ๋ฅผ ๋ฐ์ ธ๋ณด๊ฒ ๋ค. coinArr[0]
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
j - coinArr[i] ์ฐ์ฐ์ ํตํด์, ํ์ฌ ์ธ๋ฑ์ค์์ ํ์ฌ ๋์ ๊ฐ์น๋ฅผ ์ฐจ๊ฐํ์ ๋, (ํ๋ ์ถ๊ฐํ๋ค๋ ์ํฉ) ์ฐจ์ก์ด remain ์ ์ ์ฅ๋๋ค.
์ธ๋ฑ์ค๊ฐ 3์ธ ๊ฒฝ์ฐ๋ฅผ ์๋ก ๋ค์๋ฉด, j ๋ 3์ด๊ณ , coinArr[i]๋ 1์ด๋ค. ๊ทธ๋ฌ๋ฏ๋ก remain ์ 2๊ฐ ๋๋ค.
dp[j] = std::min(dp[j], 1 + dp[remain])
์ด ์ฐ์ฐ์ ๋ณด๋ฉด, ๊ฒฐ๊ตญ ํ์ฌ ์ธ๋ฑ์ค์ ํด๋นํ๋ ๊ฐ์ ๋ง๋ค ์ ์๋ ๋์ ์ต์ ๊ฐ์ (dp[j]) ๋ ํ์ฌ ๋์ ์ ๋นผ๊ณ ๊ณ์ฐํ๋ ๊ฒฝ์ฐ (dp[j]) ์, ํ์ฌ ๋์ ์ ํฌํจํ๋ ๊ฒฝ์ฐ (1 + dp[remain]) ์ค ๋ ์์ ๊ฐ์ผ๋ก ๋์ฒด๋๊ฒ ๋๋ค.
์ธ๋ฑ์ค 3์ ๊ฒฝ์ฐ๋, ์ด์ ๊ฐ์ธ 987654321 ์, ํ์ฌ ๊ฐ์ธ 1 + dp[2] = 3 ์ค ์ต์ ๊ฐ์ธ 3 ์ด ์ ์ฅ๋๋ค.
๋์ ๊ฐ์น 5์ ๊ฒฝ์ฐ ( coinArr[1] )
0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 6 | 3 |
๋์ ๊ฐ์น 12์ ๊ฒฝ์ฐ ( coinArr[2] )
0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 | 1 | 2 | 3 | 3 |
๋ง์ง๋ง์ ๊ฒฝ์ฐ, ๊ธฐ์กด dp[15] ๊ฐ 3 ์ด์๊ณ , ์๋กญ๊ฒ ๊ณ์ฐํ 1 + dp[3] ์ด 4 ์ด๋ฏ๋ก ์ต์ ๊ฐ์ธ 3์ด ์ ์ฅ๋๋ค.
๋ง์ง๋ง ์ผํญ์ฐ์ฐ์ ์ฐ์ฐ์ ํตํด, ๋ง์ง๋ง ๊ฐ์ด ์ฒ์ ๊ทธ๋๋ก 987654321 ์ด๋ผ๋ฉด ํ์ฌ ๊ฐ์ง ๋์ ์ผ๋ก ๋ง๋ค ์ ์๋ค๊ณ ํ๋จํ์ฌ -1 ์ ์ถ๋ ฅํ๊ณ , ๊ฐ์ด ๋ณ๊ฒฝ๋์๋ค๋ฉด ๊ทธ ๊ฐ์ด ์ต์ข ๋ต์ผ๋ก ํ๋จํ์ฌ ๊ทธ ๊ฐ์ ์ถ๋ ฅํ๋ค.
์ฆ, ๋ฌธ์ ์ ์ฃผ์ด์ง ํ ์คํธ์ผ์ด์ค๋ ๋ต์ด 3์ด ์ถ๋ ฅ๋๋ค.
์์ฑํ ์์ค์ฝ๋๋ ๋ค์๊ณผ ๊ฐ๋ค.
์์ฑ ์ธ์ด: C++
#include <cstdio>
#include <algorithm>
int main(){
int coinNum, priceNum;
int coinArr[101] = {0, };
int dp[10001] = {0, };
scanf("%d %d", &coinNum, &priceNum);
for (int i = 0; i < coinNum; ++i) {
scanf("%d", &coinArr[i]);
}
std::sort(coinArr, coinArr+coinNum); // ์
๋ ฅ๋ฐ์ ๋์ ๊ฐ์น ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
dp[0] = 0;
for (int i = 1; i <= priceNum; ++i) {
dp[i] = 987654321;
}
for (int i = 0; i < coinNum; ++i) {
for (int j = coinArr[i]; j <= priceNum; ++j) {
int remain = j - coinArr[i];
dp[j] = std::min(dp[j], 1 + dp[remain]);
}
}
printf("%d\n", dp[priceNum] == 987654321 ? -1 : dp[priceNum]);
return 0;
}
๐ ๋ฐฐ์ด ์
์ฒ์์๋ dp ๋ฐฐ์ด์ 2์ฐจ์ ๋ฐฐ์ด๋ก ์ ์ธํ์ฌ, ์ ๋ ฅ์ผ๋ก ๋ฐ์ ๋์ ๊ฐ์น๋ง๋ค ๊ฐ๊ฐ ํ ์ด์ฉ ํ์ฌ ๊ณ์ฐํ๋ค.
๋ฌธ์ ์ ๋์จ ํ ์คํธ์ผ์ด์ค๋ ์ ๋ต์ผ๋ก ๋์ค๊ณ , ๋ด๊ฐ ๋ง๋ ํ ์คํธ์ผ์ด์ค๋ ๋ค ์์๋๋ ์ ๋ต์ด ๋์ค๋, ์ ์ถํ๋ฉด ๊ณ์ํด์ ์ค๋ต์ด ๋์๋ค.
๋ค๋ฅธ ์ฌ๋๋ค์ ํ์ด๋ฅผ ์ฐธ๊ณ ํ๋, 1์ฐจ์ ๋ฐฐ์ด๋ก ์ ์ธํ์ฌ๋ ๋์ฑ ๊ฐ๋จํ๊ฒ ์ฒ๋ฆฌํ ์ ์์๋ค.
๋ ์ญ์๋ 1์ฐจ์ ๋ฐฐ์ด๋ก ๋ค์ ์ง๋ณด๋ ํ๋ฒ์ ์ ๋ต์ฒ๋ฆฌ๋ฅผ ๋ฐ์๋ค..
๋ค๋ฅธ ๋ 2์ฐจ์ ๋ฐฐ์ด๋ก๋ ์ฒ๋ฆฌํ๋ ์ฐ์ต์ ํด๋ด์ผ๊ฒ ๋ค.