BOJ 17626 - Four Squares #2

지난 시간에 이어 다른 사람의 풀이를 보고 다시 짜 봐도

동일하게 시간 초과가 난다.

 

그래서 C++로 제출했더니 성공..

 

아무래도 python에서 list 접근하는 시간이 C++에 비해 더 걸리는 걸로 보인다.

따라서 DP로는 풀기 힘들고, 브루트 포스로 풀어야 한다.

 

랑그라주의 법칙에 따라 제곱수로 이뤄진 게 4개 초과로 있을 수 없어서

그 조건을 활용해서 소스를 짜면 된다.

 

1. n이 제곱수인 경우 : 1 출력

2. n이 2개의 제곱수로 이뤄진 경우 : 2 출력

 - n의 절반의 제곱근 까지만 순회
 - 두 개의 제곱수가 아닌경우 n에서 두개의 제곱수를 뺀 뒤 소수점 이하면 3 출력

 - 상기의 조건에 걸리지 않으면 4 출력

 

상기의 내용을 코드로 옮기면 다음과 같다.

def solve(n):
    if int(n ** 0.5) ** 2 == n:
        return 1
    ar = []
    for i in range(1, int((n // 2) ** 0.5) + 1):
        for j in range(1, int((n - i ** 2) ** 0.5) + 1):
            if i ** 2 + j ** 2 == n:
                return 2
            elif (n - i ** 2 - j ** 2) ** 0.5 % 1 == 0:
                ar.append(3)
            else:
                ar.append(4)
    return min(ar)

print(solve(int(input())))

뭔가 풀이를 보고 풀긴 했지만

찝찝한 마음이 남는 문제였다.. 그냥 DP로 했을 때 통과되었으면 좋았을 텐데 아쉽!