백준 1669번(파이썬):제곱수의 합
백준 1669번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/1699
문제 내용
나의 풀이
import math
N=int(input())
dp=[0]*(N+1)
def check(num):#제곱수 판단 함수
root=math.sqrt(num)
res=root-int(root)
if res==0:
return True
else:
return False
for i in range(1,N+1):
if check(i):#제곱수인 경우 1개
dp[i]=1
continue
for j in range(1,(i//2)+1):#제곱수가 아닌 경우
if j==1:
dp[i]=dp[j]+dp[i-j]
else:
dp[i]=min(dp[i],dp[j]+dp[i-j])
print(dp[N])
우선 제곱수인지 판단해주는 함수를 만들었다. 그 후, N까지 이중 반복문을 통해 제곱수는 무조건 1로 하고 나머지는 반쪽만 비교를 진행하여 가장 작은 경우의 수를 구하도록 했다. 반쪽만 비교를 한 이유는 어차피 다른 반대쪽은 알아서 더해져서 비교되기 때문이다.
하지만 python에서 시간초과가 발생했고, pypy3에서는 아주 오랜시간이 걸리긴 했지만 맞긴 했다…
다른 풀이
n = int(input())
dp = [x for x 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])
안쪽 반복문의 j값을 증가시켜가며 j의 제곱수보다 작은 값일때까지 비교를 하는 방식으로 해결하는 문제였다. 제곱수를 수의 구성 요소로 더해갈 때마다 개수를 1 증가해주면서 해결한다.
제곱수를 기준으로 비교하는 방법은 생각하지 못했다…
