[백준] 1699번 제곱수의 합

 

제곱수의 합들을 구해보면 다음과 같습니다.

1 : 1
2: 1 + 1
3: 1 + 1 + 1
4: 4
5: 4 + 1
6: 4 + 1 + 1
7: 4 + 1 + 1 + 1
8: 4 + 4
9 : 9
10: 9 + 1
11: 9 + 1 + 1
12: 4 + 4 + 4

 

시도 : 실패

- 재귀함수 사용

- N보다 작거나 같은 제곱수를 빼면서 카운팅

- 반례 존재 : 12( 9+1+1+1)로 나오지만 최소개수는 3개(4+4+4)

- 시도방법은 최소개수가 아닌 단순히 제곱수들의 합으로 나타내기만 한 것

import sys
sys.setrecursionlimit(100000)

def cal_func(n, cnt):
    num = int(n**0.5)
    rest = n - (num**2)
    cnt +=1
    if rest == 0 :
        print(cnt)
    else :
        cal_func(rest,cnt)
        
n = int(input())        
cal_func(n,0)

 

 

올바른 접근법

- DP 활용

- 결과의 규칙성을 활용

- 제곱수일때는 dp[i] = 1

- 나머지는 dp[i] = dp[i-j*j] +1

- ex) 12일때 min(dp[12 -1], dp[12-4], dp[12-9]) + 1

n = int(input())
dp = [i for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,i):
        if (j*j)> i:
            break
        if dp[i] > dp[i-j*j]+1 :
            dp[i] = dp[i-j*j]+1
            
print(dp[n])

 

 

규칙성이 눈이 보이는 것 같은데 DP로 구현하는게 어렵습니다..ㅜㅜ

많이 풀어보는게 정답인듯!!!