반응형
https://www.acmicpc.net/problem/1699
코드 작성
import sys
input = sys.stdin.readline
n = int(input())
dp = [i for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, i):
if j*j > i:
break
if dp[i] > dp[i-j*j] + 1:
dp[i] = dp[i-j*j] + 1
print(dp[n])
코드 풀이
#1 점화식
점화식은 아래와 같이 구할 수 있다.
합 : i = ( i - j * j ) + ( j * j ) = i
항의 개수 : d[i] = d [ i - j * j ] 개 + 1개
# 2 예시 30의 경우
dp[30] = dp[30-5*5] +1 = dp[5] + 1
dp[5] = dp[5-2*2]+1 = dp[1] + 1
dp[1] = 1
따라서 dp[30] = dp[1] + 2 = 3
30 = 5*5 + 2*2 + 1*1
반응형
'코딩 > Python' 카테고리의 다른 글
[Python] 백준 1309 동물원 (0) | 2022.12.11 |
---|---|
[Python] 백준 15988 1, 2, 3 더하기3 (1) | 2022.12.10 |
[Python] 백준 2475 검증수 (0) | 2022.12.09 |
[Python] 백준 11053 가장 긴 증가하는 부분 (0) | 2022.12.09 |
[Python] 백준 2798 블랙잭 (0) | 2022.12.07 |