[알고리즘/동적 계획법] 17626 번 : Four Squares - python

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

17626번: Four Squares

 

---

• 문제
• 소요시간: 실패

---

• 설계하기(접근방법) 

1. n 을 입력받는다

2. 알고리즘 해석 (동적 계획법)

1) 0 = 0^2

2) 1 = 1^2

3) 2 = 1^2 + 1^2

4) 3 = 1^2 + 1^2 + 1^2

5) 4 = 2^2

6) 5 = 2^2 + 1^2

7) 6 = 2^2 + 1^2 + 1^2

8) 7 = 2^2 + 1^2 + 1^2

9) 8 = 2^2 + 2^2

10) 9 = 3^2, or 2^2 + 2^2 + 1

11 ) 10 = 3^2 + 1^2 or 2^2 + 2^2 + 1 + 1 or 

 

먼저 dp[n]이 제곱수인지 검사한다

O : 1 저장

X : 검사 진행

검사

dp[n] = dp[n - 1] + dp[1]

dp[n] = dp[n - 2] + dp[2]

dp[n] = dp[n - 3] + dp[3]..... 식으로

dp[n] = dp[n - i]  + dp[i] 식을 dp[n의 루트]까지 검사해준다

그 중 가장 작은 값이 dp[n]이 될것이다

 

ex)

dp[10] = dp[9] + dp[1] = 1 + 1

dp[10] = dp[8] + dp[2] = 2 + 2

dp[10] = dp[7] + dp[3] = 3 + 3

dp[10] = dp[6] + dp[4] = 3 + 1

dp[10] = dp[5] + dp[5] = 2 + 2

즉 이중 가장 작은 dp[9] + dp[1] = 2가 dp[10]의 값이 될 것이다.

 

중요한 점은 최소한 1개 이상의 제곱수가 포함되기에 이 제곱수를 기준으로

j^2이 n보다 작을 때 까지

dp[n - (j**2)]를 진행하여 

 

dp[11]은 dp[9] +dp[11-9] or dp[4] + dp[11-4] or dp[1] + dp[11-1] 와 같은 케이스가 나오고

이 중 가장 작은 값을 dp[11]의 값으로 정하면 된다

 

1) 1 + (dp[2]=2) = 3

2) 1 + (dp[7]=4) = 5

3) 1 + (dp[10=2) = 3

 

즉 3이 dp[11]의 값이 된다

 

3. dp[n]을 출력한다.

 

 

---

• 코드(출력)

import math
import sys

n = int(sys.stdin.readline())
dp = [0] * (n + 1)
dp[1] = 1


for i in range(2, n+1):  # 2 3 4 5 6 7
    min_val = 1e9
    for j in range(1, 50001):  # 1, 2
        if j**2 > i:
            break
        min_val = min(min_val, dp[i - (j ** 2)])
    dp[i] = min_val + 1

print(dp[n])

 

---

• 얻어갈 부분

1. 동적 계획법은 아직 어려운것 같다. 식을 쪼개려면 어떤 아이디어가 필요한지 깊게 생각해야겠다

2. 최소값을 구하는 경우 min_val = min(min_val,x)와 같은 형태로 선언하면 편리하다