[백준🥈3] #17626 Four Squares (Python)

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

예제 입력 1

25

예제 출력 1

1

예제 입력 2

26

예제 출력 2

2

예제 입력 3

11339

예제 출력 3

3

예제 입력 4

34567

예제 출력 4

4

 

✔️ Code

n = int(input())

dp = [0, 1]

for i in range(2, n+1):
    min_value = 4
    for j in range(1, int(i ** 0.5) + 1):
        min_value = min(min_value, dp[i-(j ** 2)])

    dp.append(min_value + 1)

print(dp[n])

 

✏️ Comment

브루트포스 연습할 때 풀었던 문제인데, 지금보니 그때도 Dp로 구글링해서 참고했던 것 같다.. 하여튼 기억도 안나고 해서 다시 풀어봤는데 여전히 규칙을 못 찾겠던.. ^^ 빡대가린가.. ㅠㅠ 그래서 결국 또다시 구글링을 했다........ 저번엔 제대로 이해 못했던 듯 싶다. 이번엔 제대로 이해했다!

제곱수들의 합으로 이루어진 n이 존재하고, 그 제곱수들의 개수를 구해야 하는 문제이다. 예를 들어서 dp[8]의 경우 8 이전에 존재하는 제곱수는 1, 4가 있다. 그러므로 dp[8]의 개수를 셀 수 있는 경우는 dp[1] + dp[7], dp[4] + dp[4]가 존재하는데 이를 구하기 위해선 n에서 각 제곱수들을 빼준 수의 dp값(여기서는 dp[7], dp[4]) 에다가 제곱수의 dp 값인 1을 더해주면 된다. (dp[1] = 1, dp[4] = 1)

 즉, i에서 빼주기 위한 j의 범위는 1부터 int(i ** 0.5)까지의 수이고, i에서 제곱수들을 빼주는 식은 dp[i-(j ** 2)]이다.  (여기서 i가 8이므로 int(i ** 0.5)는 2가 되니까 j의 범위는 1부터 2)

j = 1 -> dp[8-1] = dp[7]

j = 2 -> dp[8-4] = dp[4]

for문을 돌면서 이들 중 최솟값을 찾고 min_value에 저장해준 뒤 마지막으로 + 1을 해서 dp배열에 append해주면 그 값이 해당 숫자의 제곱수들의 최소 합이 된다. 그리고 문제에서 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현될 수 있다고 했기 때문에 min_value 의 초기값을 4로 지정해주었다.