[파이썬] 백준 17626 : Four Squares

[파이썬] 백준 17626 : Four Squares

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

17626번: Four Squares

실버 4

DP, 브루트포스

---

접근

 

DP문제에 대한 자신감을 박살내버리는 문제였다. 다른 사람 풀이를 보고도 좀처럼 이해가 되지 않아 골머리를 앓았다.

 

문제에 따르면 어떤 수든 간에 최대 4개가지의 제곱수의 합으로 표현이 된다고 해서 1부터 쭉 공책에 써봤다.

1 = 1^2 = 1개

2 = 1^2 * 2 = 2개

3 = 1^2 * 3 = 3개

4 = 2^2 = 1개

5 = 2^2 + 1^2 = 2개

6 = 2^2 + 1^2 * 2 = 3개

7 = 2^2 + 1^2 * 3 = 4개

8 = 2^2 * 2 = 2개

...

 

맨 왼쪽 항에 있는 값이 N이라고 할때, N보다 작은 제곱수 중 가장 큰 수에다가 다른 제곱수를 합하는 것이라고 생각했다. 그래야 최솟값이 나올 것이라고 생각했기 때문이었다.

그런데 23의 경우, 23보다 작은 제곱수 중 가장 큰 수는 16인데, 16을 포함할 때는 제곱수의 개수를 4개이하로 만들 방법이 없었다.

23 = 3^2 + 3^2 + 2^2 + 1^2

이와같이 23보다 작은 제곱수 중에 가장 큰 값이 아니더라도 제곱수의 개수가 최솟값이 되지 않는 경우가 존재했다.

 

그래서 다른 접근이 필요했다.

 

예를들어 24의 제곱수들의 최소 개수를 구한다고 가정하자.

만약 24에서 제곱수만큼의 값이 부족하다면 제곱수를 하나만 더 추가하면 될 것이다.

24보다 작은 제곱수 1, 4, 9, 16을 24에서 뺀 값은 23, 20, 15, 8가 된다.

dp와 메모이제이션을 활용해 23, 20, 15, 8까지의 제곱수의 개수를 알고 있다면, 이들 중 최솟값을 가지고 있는 것에서 1만 추가하면 우리가 구하고자 하는 값을 바로 구할 수 있다. (제곱수를 하나 더 추가해서 24를 만드는 것이므로)

 

코드(pypy)

import sys;
N = int(sys.stdin.readline())
dp = [0] * (N+1)
dp[1] = 1

for i in range(2, N+1):
    if int(i ** 0.5) == i ** 0.5:    # 루트 i를 정수형으로 형변환 한 값이 루트 i와 같다는 것은 제곱수들만 추려낸다는 것과 같다.
        dp[i] = 1    # 제곱수는 1개로 값을 완성시킬 수 있으므로 1로 초기화한다.
        continue

    j = 1
    min_ = 1e9
    while (j**2) <= i:
        min_ = min(min_, dp[i - (j**2)])    # i에서 제곱수를 뺀 숫자에 해당하는 인덱스 값들 중 가장 최솟값을 선택
        dp[i] = min_ + 1    # 제곱수만큼 수가 모자란 상태이므로 제곱수들중 어떤 값을 넣든 1개가 추가된다.
        j += 1

print(dp[N])