[알고리즘/DP] 1699번 : 제곱수의 합 - python

링크 : https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

---

• 문제
• 소요시간: 42분 25초 실패

 

---

• 설계하기(접근방법) 

1. 입력받기

숫자를 하나 입력받는다

 

2. 구현하기

백트래킹으로 오해해서 풀다가 낭패를 봤다

그리디하게 문제를 푼 이유였는데

 

타겟 숫자보다 작은 수 중

가장 큰 제곱수 부터 빼면 답이 나올 줄 알았는데

 

6100의 경우

4900을 빼주어 해나가는게 아닌

 

3600 + 2500의 형태로도 가능하다

 

따라서 수열을 써서 규칙을 찾으려고 했다

0 = x

1 = 1
2 = 1 + 1
3 = 1+1+1
4 = 1+1+1+1(x), 2
5 = 2 + 1
6 = 2 + 1 + 1
7 = 2 + 1 + 1+ 1
8 = 2 +2
9 = 3
10 = 3 + 1
11 = 3 + 1 +1
12 = 3 + 1 + 1 +1 (x) , 2 + 2 +2

 

알 수 있는 점은

처음에는 1 전의 dp만 검사하면서 1씩 늘려갔지만

제곱수가 새로 나온 시점 즉 4부터는

dp[i -4]  전의 배열에 + 1을 하여 새로 업데이트 할 수 있었다

9 역시 마찬가지였다

 

따라서 새로운 제곱수가 업데이트 되는 시점에는

제곱수들 전만 dp 검사를 하며 진행하면 된다

 

3. 출력하기

dp[n]을 출력한

 

---

• 코드(출력)

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

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

print(dp[n])

---

• 얻어갈 부분

1. 백트래킹 문제와 dp 문제를 헷갈리지 말고 엄밀하게 테스트를 해본 후 풀이를 정하자