[python]백준 1699번 : 제곱수의 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	20321	8384	6181	41.113%

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

 

나의 답

import math

def subMaxPow(n,arr):
    if n==2:
        arr.append(1)
        arr.append(1)
        return arr

    m = int(math.sqrt(n)))
    arr.append(m)

    return subMaxPow(n-pow(m,2))


num = int(input())
print(subMaxPow(num))

틀렸습니당

그냥 해당 수보다 작은 최대의 제곱수를 계속 빼가면서 1이 나올 때까지 반복

import math

def isitPow(thing):
    if not(math.sqrt(thing)-int(math.sqrt(thing))): # 제곱수라면
        return 1
    else:
        return 0

def subMaxPow(n,l):
    if isitPow(n):
        return l+1
    elif n==0 or n==1 or n==2 or n==3:
        return l+n

    tmp_arr = list()
    m = int(math.sqrt(n))
    half_n = int(math.sqrt(n/2))
    for i in range(half_n,m+1):
        tmp_arr.append(i)

    min = 987654321
    for obj in tmp_arr: # 최대 N^(1/2)
        tmp = subMaxPow(n-pow(obj,2),l+1) # 최대 깊이 logn
        if tmp<min:
            min = tmp

    return min


num = int(input())
tmp = subMaxPow(num,0)
print(tmp)

시간 초과

'루트 1/2*N 이상 루트 N 이하'의 수들을 가지고, 하나씩 접근하면서 제곱 수를 빼는 방식으로 재귀함수를 구현

수의 후보는 최대 '루트 N' 개이고, 재귀함수의 깊이가 최대 'log n'이어서, 시간 복잡도는 N^(1/2*logn) 이다. N의 범위가 최대 10^6 까지 이므로 너무 많은 시간이 걸린다.

결국 풀지 못하였음

 

다른 답

다이나믹 프로그래밍을 이용하는 문제

입력된 수 이전까지의 제곱수를 이용해서 해당 수를 표현하며, 표현한 수는 주어진 범위 값인 100,000의 루트값인 317까지만 저장한다.

https://pacific-ocean.tistory.com/205?category=810810

 

깨달은 점

완전 탐색 => 분할 정복으로 가는 생각의 흐름은 좋았지만,

1. 제발 모르겠으면 1부터 써보면서 규칙을 보자
2. 다 무식하게 계산하는 것도 생각해봤으면 (완전 탐색), 다 무식하게 저장하는 것도 생각해보자 (다이나믹 프로그래밍)