(백준 알고리즘 문제풀이) 1699번 제곱수의 합

문제

 

문제 링크

 

문제 접근

• DP를 이용하여 제곱수가 N보다 작은 자연수보다 작거나 같게하여 최소한의 제곱수를 사용한다.

코드

import sys

N = int(sys.stdin.readline())

dp = [i for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, i):
        if pow(j, 2) > i:
            break
        if dp[i] > dp[i - pow(j, 2)] + 1:
            dp[i] = dp[i - pow(j, 2)] + 1

print(dp[N])

느낀점

루프 안에 조건 문을 합쳐서 깔끔하게 만들어 보려고 했으나 그것은 실해했다. break로 루프를 빠져 나가야 시간 초과가 뜨지 않는다. 이 부분에 대하여 아시는 분 계시다면 댓글 남겨주시면 감사하겠습니다. 아직 너무 모르는게 많네요. 발전해야겠습니다ㅠㅠ..