π£ λ¬Έμ μ΄ν΄
1. μ΄λ€ μμ°μ N μ κ·Έλ³΄λ€ μκ±°λ κ°μ μ κ³±μλ€μ ν©μΌλ‘ λνλΌ μ μλ€.
2. μ£Όμ΄μ§ μμ°μ Nμ μ΄λ κ² μ κ³±μλ€μ ν©μΌλ‘ ννν λμ κ·Έ νμ μ΅μκ°μλ₯Ό ꡬν΄μΌ νλ€.
λμ κ³νλ²(Dynamic Programming) λ°©μμ μ¬μ©νλ€.
π νμ΄ κ³Όμ
DP λ°©μμ νμ©νκΈ°λ‘ νλ©΄μ μ κ³±μκ° 1 λ‘λ§ κ΅¬μ±λμ΄μμ λ, 1, 2 λ‘ κ΅¬μ±λμ΄ μμ λ, 1, 2, 3 μΌλ‘ ꡬμ±λμ΄ μμ λ .... λ±λ±
μμ°¨μ μΌλ‘ νλ μ© ν¬ν¨νλ©° λͺ¨λ κ²½μ°λ₯Ό λ°μ Έλ³΄κΈ°λ‘ νλ€.
N μ΄ 15 μΈ κ²½μ°λ₯Ό μλ‘ λ€μ΄λ³΄μλ©΄ λ€μκ³Ό κ°λ€.
< 1 μ μ κ³±μλ€μ ν©μΌλ‘ λ§λ€ λ νμ μ >
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
κ° μΈλ±μ€κ° μ λ ₯μΌλ‘ λ°λ μμ°μ N μ΄λ€.
N = 5 μ κ²½μ° 12 + 12 + 12 + 12 + 12 = 5 μ΄λ―λ‘ λ€μ― κ°μ νμ κ°μ§κ³ μλ€.
κ·Έλ°λ° λ€λ₯Έ DP λ¬Έμ μμλ λ§μ΄ μ μ©ν μ μλ κΈ°λ²μ΄μ§λ§, μ΄λ° μκ°μ ν μ μλ€.
νμ¬ 1μ μ κ³±μλ§ λ°μ Έλ³΄λ κ²½μ° N = 5 μΌμ΄μ€λ , 12 μ ν¬ν¨νλ€λ©΄ N = 4 μΌμ΄μ€μ νμ νλλ§ λ μΆκ°νλ κ²μ΄λ€.
μ νμμΌλ‘ νννμλ©΄ dp[νμ¬μ«μ] = 1 + dp[νμ¬μ«μ - (1 * 1)] λ‘ λνλΌ μ μλ κ²μ΄λ€.
< 1, 2 μ μ κ³±μλ€μ ν©μΌλ‘ λ§λ€ λ νμ μ >
0 | 1 | 2 | 3 |
1 |
2 |
3 |
4 |
2 |
3 |
4 |
5 |
3 |
4 |
5 |
6 |
μ΄λ²μλ 2 λ ν¬ν¨νλ κ²½μ°μ΄λ€.
2 μ μ κ³±μΈ 4 λΆν° μμνλ€. λ μμ μμΈ 1, 2, 3 μ μ΄μ°¨νΌ 2μ μ κ³±μΌλ‘ ννν μ μκΈ° λλ¬Έμ΄λ€.
4 μμ 22 λ₯Ό νλ ν¬ν¨νλ©΄ λ¨μ μλ 0 μ΄ λλ€. (4 - 2 * 2) 0 μ ννν μ μλ μ κ³±μμ ν (dp[0]) μ 0 κ° μ΄λ―λ‘ μ¬κΈ°μ 1 μ λν 1 μ΄ 1, 2 μ μ κ³±μλ€μ ν©μΌλ‘ λ§λλ νμ μμ΄λ€.
κΈ°μ‘΄μ 1 λ‘λ§ κ΅¬μ±νμ¬ λ§λ μΌμ΄μ€ (12 + 12 + 12 + 12) 4κ°μ§ λ³΄λ€ λ μ μ ν (22) 1κ°μ§ λ‘ λ§λ€ μ μμΌλ―λ‘ λ체νλ€.
μμΌλ‘ μ 리νμλ©΄
dp[j] = min(dp[j] , dp[j - i * i]) μ΄ λλ€.
i κ° μ κ³±μμ΄κ³ , j λ λ§λ€κ³ μ νλ μ κ° λλ€.
μμ± μΈμ΄: C++
#include <cstdio> // c νμ€μ
μΆλ ₯
#include <algorithm> // std::min ν¨μ
#include <limits.h> // INT_MAX μμ (intμ μ΅λλ²μ)
int dp[100010] = {0, };
void solve(){
dp[0] = 0;
for (int i = 1; i * i <= 100000; ++i) {
for (int j = i * i; j <= 100000; ++j) {
int remain = j - i * i; // μ κ³±μλ₯Ό νλ ν¬ν¨νμ λ λλ¨Έμ§
dp[j] = std::min(dp[j], 1 + dp[remain]);
}
}
}
int main(){
int nNumber;
std::fill_n(dp, sizeof(dp)/sizeof(int), INT_MAX); // dp λ°°μ΄μ ν° κ°μΌλ‘ μ΄κΈ°ν
scanf("%d", &nNumber);
solve();
printf("%d\n", dp[nNumber]);
return 0;
}
π λ°°μ΄ μ
μ΄μ μ νλ©° μ μ©νλ νμ΄λ°©λ²λ€μ΄ λ μ€λ₯΄λ©° κΈλ°© μ μ©νκ² λ λ¬Έμ μλ€.
λ§μ΄ νμ΄λ³΄λ κ²μ΄ μ€λ ₯ ν₯μμ ν° λμμ΄ λκ² λ€λ μκ°μ΄ λ λ€.