[백준/Python] 17626번 Four Squares

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

17626번: Four Squares

 

문제 분석

모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 문제이다.

조건. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 1 ≤ n ≤ 50,000이다.

 

코드

 

다이나믹 프로그래밍

import math

n = int(input())
dp = [0,1]

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

print(dp[n])

 

브루트포스

import math

def fourSquares(n):
    # √n이 정수일 때
    if int(math.sqrt(n)) == math.sqrt(n):
        return 1
    # √(n - i^2)이 정수일 때
    for i in range(1, int(math.sqrt(n)) + 1):
        if int(math.sqrt(n - i**2)) == math.sqrt(n - i**2):
            return 2
    # √(n - i^2 - j^2)이 정수일 때
    for i in range(1, int(math.sqrt(n)) + 1):
        for j in range(1, int(math.sqrt(n - i**2)) + 1):
            if int(math.sqrt(n - i**2 - j**2)) == math.sqrt(n - i**2 - j**2):
                return 3
    # 남은 경우는 4
    return 4


n = int(input())
print(fourSquares(n))

 

문제 풀이

1. 자연수 n을 입력받는다.

2. dp[n]은 n을 표현하기 위한 최소 개수의 제곱수 합이다. 0과 1의 최소 개수의 제곱수 합은 0과 1이므로 dp 배열에 설정한다.

3. 이중 for문으로 i를 2부터 n+1까지의 범위를 설정하고(0과 1을 제외하고 n까지의 숫자를 모두 봐야 하기 때문에 +1), j를 1부터 i의 제곱근+1으로 설정한다.(1부터 i까지의 제곱근을 모두 봐야 하기 때문에 +1)

4. 최소 개수의 제곱수 합을 구하기 위해서 min함수를 사용한다. minValue값과 현재 dp배열 안에 값을 비교해서, 최소 개수의 제곱수 합을 구해 minValue에 넣어준다.

5. for문을 통해 구한 minValue을 해당 값의 인덱스에 넣어주고, 모든 반복문이 끝나면 마지막으로 구해진 n값을 출력하면 된다.