백준 17626 - Four Squares (Python3)

코드 (Pypy3)

INF = int(1e9) #무한히 큰 수 (10억)
n = int(input())

# DP 테이블 INF로 초기화
d = [INF] * (n+1)
d[0] = 0
d[1] = 1

for i in range(2, n + 1):  
   # d[i]가 INF가 아니면 넘김
    if d[i] != INF:
        continue
    
    k = 1
    
    while (k**2) <= i:
        
        # 점화식
        d[i] = min(d[i], d[i - (k**2)] + 1)
        k+=1
        
print(d[n])
    

문제 해설

동적 프로그래밍(이하 DP) 문제이다..! (개인적으로 가장 어려워하는 문제 유형) 모든 프로그래밍 문제들이 그렇겠지만 DP는 더더욱 연습량이 많이 필요한 것 같다.

DP의 구조를 외우다싶이 해서 문제를 풀 순 있었지만 로직 자체를 정확하게 이해하고 넘어가는게 더욱 중요한 것 같다.