[BaekJoon] 17626 Four Squares (Silver 3) - Python

문제

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

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

---

입출력 예시

 

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

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

 

입력예시1)

25

출력예시1)

1

 

입력예시2)

26

출력예시2)

2

 

입력예시3)

11339

출력예시3)

3

 

입력예시4)

34567

출력예시4)

4

---

코드

 

n = int(input()) # n 입력

def dp(a): # dp함수 작성
    nums = [0] * (a + 1) # a+1개만큼의 리스트 생성 - nums[k]의 값은 k를 제곱수의 합으로 나타낼 때 필요한 제곱수의 개수를 나타낸다.

    nums[0] = 0 # 0일때는 0
    nums[1] = 1 # 1일때는 1

    for i in range(2, a + 1): # 2부터 a까지
        val = 4 # 문제에서 제곱수는 최대 4개까지 가능하다고 했기 때문에 최대값인 4 지정
        j = 1 # while문에 사용할 변수 생성
        while j**2 <= i: # j의 제곱이 i보다 작을 때 만 반복
            val = min(val, nums[i - (j**2)]) # 위에서 설정한 val보다 nums[i - (j**2)]가 작다면 val 재설정
            j += 1 # j의 값을 1씩 증가시키면서 반복
        nums[i] = val + 1 # 위의 while문에서 구한 최소값에 1을 더하여 nums[i]에 저장

    return nums[a] # 반복이 끝난 후에 nums[a]에 해당하는 값 리턴

print(dp(n)) # dp함수 실행 결과 반환

---

실행 화면

 

---

채점 결과