제곱수의 합 1699번 백준

문제:www.acmicpc.net/problem/1699

1699번: 제곱수의 합

이 문제는 c++로 제출했을 때는 통과했는데 python3로 제출했을 때는 시간초과가 난 문제이다. 또 이상하게 pypy3로 제출했을 때는 통과했다. 풀이법은 이제 제곱형태는 1로 저장하고 그 외의 다른 것은 1부터 루트값까지 반복문을 통하여 최소값을 찾은 다음에 저장하는 방식으로 하였다.

 

import sys
N=int(sys.stdin.readline().rstrip())
dp = [100000]*100001
dp[1],dp[2],dp[3]=1,2,3
for i in range(4,N+1):
    if float(int(i**0.5))==i**0.5:
        dp[i]=1
    else:
        dp[i]=i
        for j in range(1,int(i**0.5)):
            dp[i]=min(dp[i],dp[j*j]+dp[i-j*j])
 
print(dp[N])
 

풀이는 다음 위와 같다.

n = int(input())
dp = [0]*(n+1)
for i in range(1, n+1):
    dp[i] = i
    j = 1
    while j*j <= i:
        if dp[i] > dp[i-j*j]+1:
            dp[i] = dp[i-j*j]+1
        j += 1
print(dp[n])

참고:br-brg.tistory.com/17

[Python]1699. 제곱수의 합

그래서 검색을 통해 무엇이 다른지 찾아보았다. 여기는 제곱수 판단을 i-j*j를 통해 해결하였다. 오로지 제곱수의 경우에만 dp[0]+1의 형태로 1의 값을 가지기 때문이다. 그리고 if문을 통해 현재 값보다 작은 값의 경우에만 정보가 수정이 가능하기에 잘못된 값이 덮어 쓰일 일은 없다. 크게 보면 비슷하지만 제곱수 판단과 min메소드와 if문의 차이에서 시간이 결정 된 것 같다.