[λ°±μ€-17626] Four Squares / Python
π Problem Solving/Baekjoon
https://www.acmicpc.net/problem/17626
n = int(input())
d = [0] * (n + 1)
d[0], d[1] = 0, 1
for i in range(2, n + 1):
minValue = 1e9
j = 1
while (j ** 2) <= i:
minValue = min(minValue, d[i - (j ** 2)])
j += 1
d[i] = minValue + 1
print(d[n])
ν΄μ€
DP λ¬Έμ μλ€. λ¬Έμ μμ μ¬μ©λλ κ·μΉμ λ°λ‘ μ°Ύμ§ λͺ»ν΄ κ½€λ μ λ₯Ό λ¨Ήμλ€..π°
ꡬκΈλ§μ ν΅ν΄ λ¬Έμ μ μ¬μ©λλ κ·μΉμ μ°Ύμλλ° μ΄ κ·μΉμ μκ³ λλ μ½λ ꡬνμ λ±ν μ΄λ ΅μ§ μμλ€.
κ·μΉμ λ€μκ³Ό κ°λ€.
- nλ³΄λ€ μκ±°λ κ°μ μ κ³±μλ₯Ό μ°Ύκ³ n-μ κ³±μλ₯Ό μΈλ±μ€λ‘ κ°μ§ κ°μ 1μ λν΄μ£Όλ©΄ λλ€.
>> d[i - (j**2)] + 1
λͺ¨λ DP λ¬Έμ μμ μ¬μ©λλ κ·μΉλ€μ λΉ λ₯΄κ² μ°Ύμλ΄μΌ νλλ°.. μ°μ΅μ΄ λ νμνλ€!π
'π Problem Solving > Baekjoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€-1149] RGB거리 / Python (0) | 2021.05.19 |
---|---|
[λ°±μ€-1932] μ μ μΌκ°ν / Python (0) | 2021.05.19 |
[λ°±μ€-2776] μκΈ°μ / Python (0) | 2021.05.18 |
[λ°±μ€-2343] κΈ°ν λ μ¨ / Python (0) | 2021.05.18 |
[λ°±μ€-2822] μ μ κ³μ° / Python (0) | 2021.05.18 |