[baekjoon] 백준 17626번 : Four Squares (by python 파이썬) 시간초과,dp,브루트포스

정답 code

#Four Squares
import sys

def check(n):
    # n의 제곱근이 정수라면 1출력
    if (n**0.5).is_integer() :
        return 1

    # n보다 작은 어떤 수를 뺀 수의 제곱근이 정수라면 2출력 ex(A^2+B^2)
    for i in range(1, int(n**0.5)+1):
        if (int(n-i*i)**0.5).is_integer():
            return 2
    
    #n보다 작은 어떤 제곱근의 수를 두개뺀 수의 제곱근이 정수라면 3출력 ex(A^2+B^2+C^3)
    for i in range(1,int(n**0.5)+1):
        for j in range(1, int((n-i*i)**0.5)+1) :
            if ((n-(i*i)-(j*j))**0.5).is_integer():
                return 3

    #해당하지 않을경우 4출력
    return 4

n = int(sys.stdin.readline())
print(check(n))

 

 

 

시간초과 code

-dp사용

#Four Squares

n = int(input())
d = [0]*(n+1)
d[1] = 1

for i in range(2,n+1):
    j = 1
    min_cnt = 4

    while((j**2)<=i):
        a = d[i-(j**2)]
        min_cnt = min(min_cnt,a)
        j += 1

    d[i] = min_cnt+1

print(d[n])

 

solution

dp방식은 pypy3방식으로 제출하지 않는이상 시간초과가 발생하여 브루트포스 방식으로 해결하였다.

 

1: n의 제곱근이 정수인경우 = 1    ex) 16 = 4**2, 64 = 8**2

2: n보다 작은 어떤 수를 뺀 수의 제곱근이 정수인경우(A^2+B^2)  =2    ex)17 - 4**2 = 1**2,  40 - 6**2 = 2**2

3: n보다 작은 어떤 제곱근의 수를 두개뺀 수의 제곱근이 정수인경우(A^2+B^2+C^3)  =3  ex)49 - 6**2 - 3**2 = 2**2 

4: 나머지 경우