[Python] BOJ/백준 17626번 Four Squares

[문제]

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

17626번: Four Squares

 

[풀이]

문제를 읽었을 때 딱 봐도

제곱 반복 수행 -> 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용 -> 동적 계획법!!!

그렇다면 이제 문제에 사용되는 규칙을 찾아야 한다.

 

 

	0	1	2	3	4	5	6	7	8
1	0	1	2	3	1	5	6	7	8
2	0	1	2	3	1	2	3	4	2
3	0	1	2	3	1	2	3	0	0
4	0	1	2	3	1	2	3	0	0

dp의 2열의 1은 한 개의 제곱수로 사용했을 때 표현할 수 있는지를 나타낸다. 5는 제곱수가 아니므로 5로 초기화한다.

 

3열은 2개의 숫자를 사용했을 때 필요한 개수이다. 5를 두 숫자로 표현하면 (1, 2), (2, 3)으로 표현할 수 있는데, dp값을 더했을 때 값이 2이므로 5는 2개의 제곱수를 사용했을 때 2개를 더하면 만들어진다. 이렇게 차례대로 전체를 업데이트했을 때 필요한 제곱수의 최소 개수를 업데이트할 수 있다.

 

4열은 3개의 숫자를 사용했을 때의 개수이다. 이미 dp에 있는 값은 그 숫자를 표현하기 위해 필요한 최소 숫자의 개수로 이루어져있다. 따라서 업데이트를 할 경우 자동으로 최소 개수로 업데이트된다.

 

문제에서 얘기한 대로 넷 혹은 그 이하의 제곱수의 합으로 표현해야 하기 때문에 4개의 숫자를 사용했을 때까지 업데이트를 하면 답이 나온다.

---

 

예를 들어 9에서 발생하는 최소 개수를 만들기 위해서는

1. (8에서 발생하는 최소 개수 + 1에서 발생하는 최소 개수)
2. (5에서 발생하는 최소 개수 + 4에서 발생하는 최소 개수)
3. (3에서 발생하는 최소 개수 + 0에서 발생하는 최소 개수)

를 비교하면 된다.  따라서 n보다 작거나 같은 제곱수를 찾은 후 (n-제곱수)를 인덱스로 가진 값에 1을 더해준다.

-> dp[i - (j**2)] + 1

 

[코드]

import math
import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1

    for i in range(2, n+1):
        min_value = 1e9
        for j in range(1, int(math.sqrt(i)) + 1):
            min_value = min(min_value, dp[i - j ** 2])
        dp[i] = min_value + 1
    print(dp[n])