[1699. 제곱수의 합]

링크텍스트

이번 문제는 Dynamic Programming으로 조그만 응용을 해보는 문제였다.
어떤 숫자 N이 주어졌을 때, 가장 적은 개수의 제곱수의 합으로 나타내자는 어찌보면 간단한 논리였지.

이번에는 치팅 없이 내 뇌 안에서만 뽑아내려고 노오력 했으나, 어김없이 뜨는 에러 "시간초과"
꺼이꺼이.. 퓨퓨ㅜㅜㅜㅜㅜ
그 코드가 뭔지 한번 파헤쳐 보자면, 아래와 같다.

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

# 정답 리스트 생성, 제곱수 항은 1로 고정하기
dp = [k for k in range(N+1)]
for l in range(1,N+1):
    if l*l <= N:
        dp[l*l] = 1
        
# dp로 각 항 업데이트 해주기
for i in range(1,N+1):
    for j in range(1,N+1-i):
        if i + (j*j) <= N:
            dp[i+(j*j)] = min(dp[i+(j*j)], dp[i]+1)
        if i + (j*j) > N:
            continue
print(dp[-1])

원인을 뇌피셜로 생각해보자면, for 문을 2개 돌아서 O(N^2)가 되었는가?
: 흠 이게 직접적인 해결이 될 지는 모르겠으나,

잠정적으로 시간초과를 일으킨 문제는 :

1___
min 함수의 사용

2___
break 써야 할 자리에 continue를 박은 것 : 한번 i+(j*j)가 N을 초과하면 바로 탈출해야 함.

그래서 아래 코드와 같이 개선을 해보았다. min 함수를 풀어주고, break를 넣어서 계산의 시간을 줄임.

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

# 정답 리스트 생성, 제곱수 항은 1로 고정하기
dp = [N for _ in range(N+1)]

# dp로 각 항 업데이트 해주기
for i in range(1,N+1):
    if i*i <= N:
        dp[i*i] = 1
    for j in range(1,N+1-i):
        if i + (j*j) > N:
            break
        else:
            if dp[i+(j*j)] > dp[i]+1:
                dp[i+(j*j)] = dp[i]+1
print(dp[-1])