[백준1699번] 제곱수의 합 / Python3

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력 1

7

예제 출력 1

4

나의풀이

이 문제는 2293번 동전 1 문제와 매우 비슷했다. 동전 1 문제를 보면 dp배열의 행을 동전의 가치, 열을 원하는 값까지의 0부터 증가하는 값으로 놓고 풀었다. 이 문제에서는 열은 같지만 행을 1부터 입력받는 N값의 제곱근까지의 값을 두고 동전 1문제와 같은 방식으로 풀면된다.

이 문제를 우선 이해하기 쉽게 2차원 배열로 생각을 해보면 다음과 같은 점화식을 생각해낼 수 있다.

1. dp[i][j] = dp[i-1][j]        // if j < (i^2)
2. dp[i][j] = min(dp[i-1][j], dp[i][j-(i^2)] + 1)  // if j >= (i^2)

1번의 경우 : 이 상황은 i의 제곱값이 j보다 작을때는 i의 제곱을 더할수가 없다는 의미이므로 바로 전값인 i-1에서의 값을 그대로 가져오면 된다.

2번의 경우 : 이때에는 위에 1번의 경우와 j에서 i의 제곱만큼 뺀값일때의 최솟값에 1을 더한 값 중 작은 값을 넣어주면 된다.

단, 2차원 배열 그대로 문제를 제출하면 메모리 초과가 나오게된다. 이 문제도 동전 1문제와 같이 j의 시점에서 i-1행에서도 j보다 큰 인덱스의 값은 건드리지않는다. 따라서 1행의 dp배열을 가지고 값을 최신화시켜가면서 문제를 해결할 수 있다.

코드

# 1699번 제곱수의 합
import math

# main
n = int(input())
root_n = int(math.sqrt(n))        // 제곱근을 구해 int형으로 내림.

dp = [0 for _ in range(n+1)]    // 1차원배열 사용.

for i in range(1,root_n+1):
    if i == 1:                                    // i가 1일때 초기화 작업
        for j in range(1,n+1):
            dp[j] = j
    else:
        for j in range(1,n+1):
            if j - (i**2) < 0:
                dp[j] = dp[j]
            else:
                dp[j] = min(dp[j-(i**2)]+1, dp[j])
print(dp[-1])