[🥈3 / 백준 1699 / 파이썬] 제곱수의 합

 

1699번: 제곱수의 합

 

문제

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

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

입력

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

출력

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

 

예제 입력 7

예제 출력 4

 

풀이

 

처음엔 단순히 n이 주어졌다면, n이 0이 될 때까지 n을 넘지 않는 가장 큰 제곱수로 뺀 횟수를 구하면 될 것 같았다.

 

import math
n = int(input())
r = 0
while(n > 0):
    r += 1
    n -= int(math.sqrt(n))**2
print(r)

 

예제는 통과했으나, 항상 가장 큰 제곱수부터 빼기 때문에 최적해를 구할 수 없었다.

위 코드로 43의 제곱수의 수를 구한다면 6² + 2² + 1² +1² + 1² 으로 5개가 나오는데

43은 5² + 3² + 3² 으로 3번 만에 구할 수 있기 때문이다.

 

따라서 다이나믹 프로그래밍을 통해 문제를 해결하고자 했다.

 

 

2번째로 시도한 방법은 우선 길이 n+1의 dp배열을 만들고

그곳에 모든 n 이하의 수에 대해 제곱수의 수를 구하는 방법이었다.

 

우선 선작업으로 n을 넘지 않는 제곱수들의 인덱스를 1로 채워준다.

그리고 dp를 순서대로 채워나가는데, 현재까지 구한 수들의 제곱수 개수를 더해가며 합이 가장 적은 것을 고르게 했다.

만약 n이 10이라면 1+9, 2+8, …, 5+5 중 제곱수의 개수가 가장 적은 것을 고르는 방법이었다.

 

n  = int(input())
dp = [0 for i in range(n+1)]
a = 1
while(n >= a**2):
    dp[a**2] = 1
    a+=1

a = 0
while(n > a):
    a+=1
    if dp[a] != 0:
        continue
    temp = float('inf')
    for i in range(1,a//2+1):
        b = dp[i]+dp[a-i]
        if b == 2:
            dp[a] = b
            break
        if temp > b:
            temp = b
    else:
        dp[a] = temp
print(dp[-1])

 

답은 맞게 나오나, 시간초과가 문제였다.

배열 N개를 돌며 N/2 만큼의 수들을 비교하다보니 시간복잡도가 약 O(N^2)이 되는 것 같았다.

 

이 방법으로 해결하기엔 N이 너무 컸다.마땅한 방법이 없을까 하고 테스트 케이스를 돌리는데, 되짚어보니 제곱수의 개수가 4를 넘은 적이 없던 것 같았다.이전에 다른 문제를 풀 때, 모든 자연수는 4개 이하의 제곱수의 합으로 표현할 수 있다는 것을 본 적이 있었던 것 같았다.그래서 dp배열을 max로 직접 확인해보았더니 역시나 4가 최대였다!

 

 

여기서 아이디어를 얻어 dp를 각 수들로 10만개를 구성하는 것이 아닌제곱수의 개수별로 만들 수 있는 수들을 메모이제이션하기로 했다.

 

위에서 했던 방법과 같이 제곱수 1개로 만들 수 있는 수들은 직접 채워넣어주었다.그리고 제곱수 2개로 만들 수 있는 수, 3개로 만들 수 있는 수들을 백트래킹을 통해 구했다.만약 수들을 만들다 n과 같은 수가 나온다면 현재 구성한 제곱수의 개수를 출력하고 프로그램을 종료했다.

 

제곱수 3개로 만들 수 있는 수를 모두 다 구했는데도 답이 없다면 무조건 4개이므로 4를 출력하고 프로그램을 종료했다.

 

import sys
n  = int(input())
dp = [[] for i in range(4)]
a = 0

# 제곱수 1개로 만들 수 있는 수
while(n >= a**2):
    a+=1
    a2 = a**2
    if a2 == n:
        print(1)
        sys.exit()
    dp[0].append(a2)

# dp자리, 사용가능한 제곱수의 개수, 합, 백트래킹을 위한 조건
def bt(num,cnt,nsum,start):
    if cnt == 0:
        if nsum == n:
            print(num+1)
            sys.exit()
        global dp
        dp[num].append(nsum)
        return
    
    for i in range(start,len(dp[0])):
        bt(num,cnt-1,nsum+dp[0][i],i)
        
bt(1,2,0,0)
bt(2,3,0,0)
print(4)

 

 

2021-09-16 수정

 

브루트 포스만 활용해도 잘 풀린다. 심지어 시간도 더 적게 든다.

괜히 어렵게 돌아간게 아닌가 싶다.

 

n = int(input())

minCount = 4

def bf(n, count):
    global minCount
    
    if n == 0:
        minCount = min(minCount, count)
        return
    if count > minCount:
        return
    for i in range(int(n ** 0.5),int((n//(4-count)) ** 0.5),-1):
        bf(n - i**2,count+1)
    
bf(n,0)
print(minCount)