https://www.acmicpc.net/problem/17626
μμ΄λμ΄
1. 그리λμ dp
- μ²μμλ nμ λμ§ μλ μ΅λ μ κ³±μλ₯Ό nμ λΉΌκ°λ©΄ λμ§ μμκΉ μκ°νλ€.
- μ΄λ κ² νλ©΄ μμΈκ° μκΈ΄λ€. μλ₯Ό λ€μ΄ 12λ 그리λλ‘ μκ°νλ©΄ 9, 1, 1, 1μ΄μ§λ§ μ λ΅μ 4,4,4λ‘ 3κ°κ° μ΅μ κ°μλ€.
- λ€μ λ¬Έμ λ΄μ©μ λ³΄κ³ dpλ‘ νκΈ°λ‘ κ²°μ
- DP[n] = (nμ΄λΌλ μλ₯Ό λ§λλλ° νμν μμ κ°μ)
μ½λ μ€λͺ
k = 1
while k**2 <= n:
DP[k**2] = 1
k += 1
λ¨Όμ DP리μ€νΈμ μ κ³±μλ€μ μ μ₯ν΄μ€λ€. 1, 4, 9... λ μ κ³±μμ΄λ―λ‘ λ¬΄μ‘°κ±΄ μ΅μ κ°μλ 1μ΄λ€.
for i in range(1, n + 1):
if DP[i] != 0:
continue
j = 1
while j*j <= i:
if DP[i] == 0:
DP[i] = DP[j*j] + DP[i - j*j]
else:
DP[i] = min(DP[i], DP[j*j] + DP[i - j*j])
j += 1
nκΉμ§ forλ¬Έμ μ€ννλ€. DPμ μ΄λ―Έ κ°μ΄ μ‘΄μ¬νλ©΄(= μ κ³±μ λΌλ©΄) continue ν΄μ€λ€.
DPμ κ°μ΄ μλ€λ©΄ iλ₯Ό λμ§ μλ μ κ³±μκΉμ§ λ°λ³΅ν΄μ£Όλ©΄ λλ€.
μλ₯Ό λ€μ΄ iκ° 12λΌλ©΄
DP[12] = DP[1] + DP[11]λ₯Ό λ¨Όμ μ μ₯ν΄μ€λ€.
μ΄νμλ
DP[4] + DP[8], DP[9] + DP[3]κ³Ό λΉκ΅ν΄μ μ΅μκ°μ μ μ₯ν΄μ€λ€.
μ¬κΈ°μ μ κ³±μλ€μ μ λΆ 1μ΄λ―λ‘ DP[i] = min(DP[i - j * j]) + 1 (j*j <= i)λΌκ³ μκ°νλ©΄ λλ€.
μ 체 μ½λ
n = int(input())
count = 0
DP = [0] * (n + 1)
k = 1
while k**2 <= n:
DP[k**2] = 1
k += 1
for i in range(1, n + 1):
if DP[i] != 0:
continue
j = 1
while j*j <= i:
if DP[i] == 0:
DP[i] = DP[j*j] + DP[i - j*j]
else:
DP[i] = min(DP[i], DP[j*j] + DP[i - j*j])
j += 1
print(DP[n])
'𧩠Problem Solving > [λ°±μ€]' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 11403 κ²½λ‘μ°ΎκΈ° (python νμ΄μ¬) (0) | 2022.07.06 |
---|---|
[λ°±μ€] 16236 μκΈ° μμ΄ (python νμ΄μ¬) (0) | 2022.07.05 |
[λ°±μ€] 2293 λμ 1 (python νμ΄μ¬) (1) | 2022.07.05 |
[λ°±μ€] 2096 λ΄λ €κ°κΈ° (python νμ΄μ¬) (0) | 2022.07.04 |
[λ°±μ€] 16928 λ±κ³Ό μ¬λ€λ¦¬ κ²μ (python νμ΄μ¬) (0) | 2022.07.03 |