제곱수의 합 (BOJ-1699)

01 Mar 2021 in ALGORITHM

‘시간제한 2초, 메모리제한 128MB, BOJ-1699’

제곱수의 합 (BOJ-1699)
처음엔 그냥 풀다가 테스트케이스도 제대로 나와서 제출했더니 틀렸다고 나와서 왜 틀렸는지 이해가 안갔는데, 이런 경우를 고려하지 못했다.

12 = 3² + 1² + 1² + 1²
= 2² + 2² + 2²

이중에서 제일 항의 갯수가 적은 걸 골라야 하는데, 내가 짰던 방식은 그걸 고려하지 못했다.

이 문제는 진짜 점화식에 접근하는 방법이 너무 어려웠다;;

접근했던 방법

이 문제는 동적 계획 문제를 많이 풀어보고 수학적으로 여러 방법으로도 생각해 봐야 한다는걸 알려줬다.

막상 그 규칙을 찾으면 소스 코드의 길이는 길지 않았지만, 여기까지 오는데 많이 어려웠다.

• 1부터 값을 생각해보면 -> 1 = 1² -> 항 1개
• 2는 다음과 같다. -> 2 = 1² + 1² -> 항 2개
• 3 = 1² + 1² + 1² -> 항 3개
• 4는 1² + 1² + 1² + 1²으로 나타낼 수 있지만, 2² 항 1개로도 가능하다.
• 조금 건너뛰어서 7을 생각해보면 7은 1²을 7개 더한 걸로도 나타낼 수 있지만, 2² 1개와 1² 3개의 합으로도 가능하다.
• 8은 1²을 8개 더한 걸로도 나타낼 수 있지만, 2² 2개의 합으로도 가능하다.
• 9는 3² 1개로 가능하다.
• 10은 3² 1개와 1² 1개의 합으로 가능하다.

여기까지 봤을 때 1²으로만 이루어 지지 않은 수들을 확인하면 다음과 같다.

• 4 = 2²
• 7 = 2² + 1² + 1² + 1²
• 8 = 2² + 2²
• 9 = 3²
• 10 = 3² + 1²

이를 다시 아래와 같이 생각 할 수 있다.

• 4 = (4 - 2²) + 2² … // 4에서 2²를 빼면 0이므로, 0은 제곱수의 합으로 표현할 때 항이 0개, 거기에 2²을 추가로 붙이면 항의 갯수는 1개
• 7 = (7 - 2²) + 2² … // 7에서 2²를 빼면 3인데, 3을 제곱수의 합으로 표현한 최소 형태의 마지막에 2² 한개를 추가로 붙인다고 생각
• 8 = (8 - 2²) + 2² … // 8에서 2²을 빼면 4인데, 4를 제곱수의 합으로 표현한 최소 형태의 마지막에 2² 한개를 추가로 붙인다고 생각
• 9 = (9 - 2²) + 2² 혹은, 9 = (9 - 3²) + 3²
  • 전자의 경우, 9에서 2²을 빼면 5인데, 5를 제곱수의 합으로 표현한 최소 형태의 마지막에 2² 한개를 추가로 붙인다고 생각
  • 후자의 경우, 9에서 3²을 빼면 0이므로, 0은 제곱수의 합으로 표현할 때 항이 0개, 거기에 3² 한개를 추가로 붙이면 항의 갯수는 1개
  • 전자와 후자 중 최소를 고른다. → 9는 제곱수의 항 1개로 표현 가능

9에서 2²을 빼는 경우와 3²을 빼는 경우 2가지로 나뉘어진걸 알 수 있다.

좀 더 큰 수인 43을 확인해 보면

• 43 = (43 - 2²) + 2² = …
  • = (43 - 3²) + 3² = …
  • = (43 - 4²) + 4² = …
  • = (43 - 5²) + 5² = 18 + 5² -> 18은 3² + 3² = 2개의 최소 항으로 표시 -> 총 항의 갯수 3개
    • 43 = 18 + 5² = 3² + 3² +5² (3개)
  • = (43 - 6²) + 6² = 7 + 6² -> 7은 1² + 1² + 1² + 2² = 4개의 최소 항으로 표시 -> 총 항의 갯수 5개
    • 43 = 7 + 6² = 1² + 1² + 1² + 2² +6² (5개)

정리하면 다음과 같다.

• (1) dp[N]은 어떤 자연수 N을 제곱수의 합으로 나타낼 때 항의 최소 개수를 말한다.
  
• (2) 처음에는 모든 수들을 1²의 합으로 나타낸다고 생각하고 dp[N] = N 으로 초기화해 놓는다.
  
• (3) 어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가장 작은 것부터 뺀다.
  
• (3-1) 빼서 나온 그 수(N - 제곱수)를 제곱수들의 합으로 나타낼 때의 항의 최소 개수는 dp[N - 제곱수]이며, 여기에 제곱수 1개 항을 추가로 붙여줬을 때 총 항의 갯수는 dp[N - 제곱수] + 1 이다.
  • (ex) 11에서 3²을 뺐을 때 dp[11 - 3²] = dp[2] 이며, 여기에 제곱수 1개인 3²을 추가로 더해주는 것.

총 항의 갯수는 dp[N-제곱수] + 1 = dp[11-3²] + 1 = dp[2] + 1 = 3 이 된다.

• 11 = (11 - 3²) + 3² = 1² + 1² + 3² (항 3개)
• (4) dp[N-제곱수]+1과 기존의 dp[N]과 비교해 더 작은 값을 dp[N]에 대입한다.

    dp[N] = min(dp[N], dp[N - 제곱수] + 1)

• 다시 (3)의 과정으로 가서 그 다음 제곱수를 빼고 과정을 반복한다.
• 정리하여 말하자면, 자연수 32를 예로 들었을 때
  • dp[32-1²], dp[32-2²], dp[32-3²], dp[32-4²], dp[32-5²] 중에서 최솟값에 +1을 하면 정답이 된다.
• dp 배열을 형성하기 위해, 1부터 N까지 bottom-up 으로 반복한다. 이전 dp 값들이 이후의 값 계산에 쓰일 수 있다.

소스 코드

n = int(input())
dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = i
    for j in range(1, i):
        if j * j > i:
            break

        if dp[i] > dp[i-j*j] + 1:
            dp[i] = dp[i - j * j] + 1

print(dp[n])