[백준] 17626번 (python 파이썬)

https://www.acmicpc.net/problem/17626

 

DP 또는 완탐으로 풀수 있다.

완탐으로 문제를 해결하였다.

 

해당 숫자의 int(제곱근)부터 해당 숫자 - int(제곱근)^2 의 제곱근-1까지 반복문을 돌려서 확인하였다. 

사실 그냥 해당 숫자의 int(제곱근)부터 0까지 돌려도 풀린다.

 

import math

n = int(input())

answer = 4


def solve():
    global answer, n
    sqrt = int(math.sqrt(n))
    for i in range(sqrt, int(math.sqrt(n - sqrt ** 2)) - 1, -1):
        n -= i ** 2
        if n == 0:
            answer = min(1, answer)
        sqrt2 = int(math.sqrt(n))
        for j in range(sqrt2, int(math.sqrt(n - sqrt2 ** 2)) - 1, -1):
            n -= j ** 2
            if n == 0:
                answer = min(2, answer)
            sqrt3 = int(math.sqrt(n))
            for k in range(sqrt3, int(math.sqrt(n - sqrt3 ** 2)) - 1, -1):
                n -= k ** 2
                if n == 0:
                    answer = min(3, answer)
                elif n == 1:
                    answer = min(4, answer)
                n += k ** 2
            n += j ** 2
        n += i ** 2


solve()
print(answer)

 

범위를 0까지 했을때

import math

n = int(input())

answer = 4


def solve():
    global answer, n
    sqrt = int(math.sqrt(n))
    for i in range(sqrt, 0, -1):
        n -= i ** 2
        if n == 0:
            answer = min(1, answer)
        sqrt2 = int(math.sqrt(n))
        for j in range(sqrt2, 0, -1):
            n -= j ** 2
            if n == 0:
                answer = min(2, answer)
            sqrt3 = int(math.sqrt(n))
            for k in range(sqrt3, 0, -1):
                n -= k ** 2
                if n == 0:
                    answer = min(3, answer)
                elif n == 1:
                    answer = min(4, answer)
                n += k ** 2
            n += j ** 2
        n += i ** 2


solve()
print(answer)