[백준] 17626 Four Squares (python 파이썬)

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

17626번: Four Squares

---

아이디어

1. 그리디와 dp

• 처음에는 n을 넘지 않는 최대 제곱수를 n에 빼가면 되지 않을까 생각했다.
• 이렇게 하면 예외가 생긴다. 예를 들어 12는 그리디로 생각하면 9, 1, 1, 1이지만 정답은 4,4,4로 3개가 최소 개수다.  
•  다시 문제 내용을 보고 dp로 풀기로 결정
• DP[n] = (n이라는 수를 만드는데 필요한 수의 개수)

---

코드 설명

k = 1
while k**2 <= n:
    DP[k**2] = 1
    k += 1

먼저 DP리스트에 제곱수들을 저장해준다. 1, 4, 9... 는 제곱수이므로 무조건 최소 개수는 1이다.

 

for i in range(1, n + 1):
    if DP[i] != 0:
        continue
    j = 1
    while j*j <= i:
        if DP[i] == 0:
            DP[i] = DP[j*j] + DP[i - j*j]
        else:
            DP[i] = min(DP[i], DP[j*j] + DP[i - j*j])
        j += 1

n까지 for문을 실행한다. DP에 이미 값이 존재하면(= 제곱수 라면) continue 해준다. 

 

DP에 값이 없다면 i를 넘지 않는 제곱수까지 반복해주면 된다.

 

예를 들어 i가 12라면

DP[12] = DP[1] + DP[11]를 먼저 저장해준다.

이후에는 

DP[4] + DP[8], DP[9] + DP[3]과 비교해서 최솟값을 저장해준다.

여기서 제곱수들은 전부 1이므로 DP[i] = min(DP[i - j * j]) + 1 (j*j <= i)라고 생각하면 된다.

---

전체 코드

 

n = int(input())
count = 0

DP = [0] * (n + 1)

k = 1
while k**2 <= n:
    DP[k**2] = 1
    k += 1

for i in range(1, n + 1):
    if DP[i] != 0:
        continue
    j = 1
    while j*j <= i:
        if DP[i] == 0:
            DP[i] = DP[j*j] + DP[i - j*j]
        else:
            DP[i] = min(DP[i], DP[j*j] + DP[i - j*j])
        j += 1
print(DP[n])