백준 17626 Four Squares Python

🔷 백준 17626 Four Squares Python

✅ 문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였습니다. 어떤 자연수는 여러 가지 방법으로 표현됩니다. 예를 들어, 26은 \(5^2 + 1^2\)로 표현할 수 있고, \(4^2 + 3^2 + 1^2\)로도 표현됩니다.
역사적으로 암산 명수들에게 주어진 문제 중 하나가 바로 자연수를 네 개 이하의 제곱수의 합으로 표현하는 것이었습니다.
1900년대 초 한 암산가는 \(15663 = 125^2 + 6^2 + 1^2 + 1^2\)라는 해를 8초 만에 구했고,
더 어려운 \(11339 = 105^2 + 15^2 + 8^2 + 5^2\)는 56초가 걸렸다고 합니다.

자연수 \(n\)이 주어질 때, \(n\)을 최소 개수의 제곱수 합으로 표현하는 프로그램을 작성하세요.

• 입력: 자연수 \(n\) (\(1 \le n \le 50,000\))
• 출력: 최소 개수의 제곱수 합

✅ 문제 풀이 아이디어 정리

우리는 제곱수의 합으로 \(i\)를 표현해야 합니다.

우리가 구하려는 것은 \(i\)라는 수를 하나 이상의 제곱수들의 합으로 표현하는 방법 중, 가장 적은 제곱수 개수입니다.
즉, \(i = x_1^2 + x_2^2 + \dots\) 형태로 표현됩니다.
여기서 \(x_k\)는 각 항마다 선택된 제곱수의 밑입니다.
\(i\)가 \(1,2,3,\dots\) 순서로 증가하면서, 각 \(i\)마다 최소 제곱수 개수를 계산합니다.
예를 들어:

• \(1 = 1^2\)
• \(2 = 1^2 + 1^2\)
• \(3 = 1^2 + 1^2 + 1^2\)
• \(4 = 2^2\) 또는 \(1^2+1^2+1^2+1^2\)

\(j\)는 ‘마지막에 선택한 제곱수’를 의미합니다.

어떤 수 \(i\)를 만들 때, 우리는 마지막으로 더한 제곱수가 무엇인지 하나씩 가정합니다.
즉, \(j\)를 선택한다는 것은 수식의 맨 끝에 \(j^2\)를 붙이는 것입니다.

\(i = j^2 + x_1^2 + x_2^2 + \dots\)

만약 \(i-j^2=0\)이라면, \(j^2\) 하나로 \(i\) 전체를 설명할 수 있다는 뜻입니다.
예를 들어 \(i=4\)이고 \(j=2\)라면:
\(4 = 2^2 + 0\)
즉, \(2^2\) 하나로 \(4\)를 만들 수 있습니다.

만약 \(i-j^2>0\)이라면, 아직 남은 값을 설명하기 위해 제곱수가 더 필요하다는 뜻입니다.

\(i-j^2\)에서 남은 값을 어떻게 표현할지를 생각합니다.

\(i-j^2\)는 \(i\)에서 마지막으로 선택한 제곱수 \(j^2\)를 뺀 나머지입니다.
이 나머지를 표현하기 위해 최소 몇 개의 제곱수가 필요한지는 이미 더 작은 문제에서 계산해 둔 결과입니다.
예를 들어 \(i=4\)이고 \(j=1\)이면:
\(4 = 1^2 + x_1^2 + x_2^2 + x_3^2\)
여기서 남은 \(3\)을 만들기 위해 최소 몇 개가 필요한지는 \(dp[3]\)에 저장되어 있습니다.
이렇게 해서 \(i-j^2\)의 최소해에 \(1\)을 더하면 됩니다.

\(j\)를 하나씩 증가시키며 최솟값을 찾습니다.

가능한 모든 \(j\)를 하나씩 시도해 보면서, 각 경우마다 \(i-j^2\)의 최소해에 \(1\)을 더한 값을 계산합니다.
그리고 그중에서 가장 작은 값을 선택합니다.
예를 들어 \(i=4\)일 때:

• \(j=1\): 남은 값 \(3\) → \(dp[3]+1=4\)
• \(j=2\): 남은 값 \(0\) → \(dp[0]+1=1\)

여기서 최소값은 \(1\)입니다.

✅ \(i=1\)

원칙 1

우리는 제곱수들의 합이 \(i=1\)이 되도록 만드는 최소한의 제곱수 개수를 구해야 합니다.
즉, \(1 = x_1^2 + x_2^2 + \dots\) 형태로 표현하면서, 여기서 사용되는 제곱수의 개수가 가장 적어야 합니다.
예를 들어, \(1\)을 표현하기 위해 가능한 방법은 \(1=1^2\)입니다.
이 방법은 제곱수가 하나만 필요하므로 최적입니다.

원칙 2

\(j\)는 마지막에 더한 제곱수의 밑을 의미합니다.
여기서 가능한 \(j\)는 \(1\)뿐입니다.
즉, \(j=1\)을 선택한다는 것은, 우리가 찾는 식이 \(1=1^2+(남은 값)\)의 형태라는 뜻입니다.
남은 값은 \(1-1=0\)이 됩니다.
남은 값이 \(0\)이라는 것은, \(j^2\) 하나만으로 \(i\)를 모두 설명할 수 있다는 의미입니다.

원칙 3

남은 값 \(0\)을 표현하기 위해 필요한 최소 제곱수 개수는 이미 정의된 \(dp[0]=0\)입니다.
남은 값 \(0\)의 최소해에 마지막으로 더한 \(j^2\) 하나를 추가합니다.
즉, \(0+1=1\)입니다.

원칙 4

여기서 가능한 \(j\)는 \(1\) 하나뿐이며, 더 큰 \(j\)는 \(i\)보다 커서 불가능합니다.
따라서 최소값은 \(1\)입니다.
따라서 \(dp[1]=1\)로 업데이트됩니다.

✅ \(i=2\)

원칙 1

우리는 제곱수들의 합이 \(i=2\)이 되도록 만드는 최소한의 제곱수 개수를 구해야 합니다.
즉, \(2 = x_1^2 + x_2^2 + \dots\) 형태로 표현하면서, 사용되는 제곱수의 개수가 가장 적어야 합니다.
예를 들어, \(2=1+1\)로 표현할 수 있습니다.

원칙 2

\(j\)는 마지막에 더한 제곱수의 밑을 의미합니다.
여기서 가능한 \(j\)는 \(1\)뿐입니다.
\(j=1\)을 선택한다는 것은 \(2=1^2+(남은 값)\)의 형태라는 뜻입니다.
남은 값은 \(2-1=1\)입니다.
남은 값이 \(1\)이라는 것은 \(j^2\) 하나만으로 \(i\)를 모두 설명할 수 없고, 남은 \(1\)을 더 표현해야 한다는 의미입니다.

원칙 3

남은 값 \(1\)의 최소 제곱수 개수는 이미 계산된 \(dp[1]=1\)입니다.
이 최소해에 마지막으로 선택한 \(j^2\) 하나를 더해 \(1+1=2\)입니다.

원칙 4

가능한 \(j\)는 \(1\) 하나뿐이므로 \(dp[2]=2\)로 업데이트됩니다.

✅ \(i=3\)

원칙 1

우리는 제곱수들의 합이 \(i=3\)이 되도록 만드는 최소한의 제곱수 개수를 구해야 합니다.
즉, \(3 = x_1^2 + x_2^2 + \dots\) 형태로 표현하면서, 사용되는 제곱수의 개수가 가장 적어야 합니다.
예를 들어, \(3=1+1+1\)로 표현할 수 있습니다.

원칙 2

\(j\)는 마지막에 더한 제곱수의 밑을 의미합니다.
여기서 가능한 \(j\)는 \(1\)뿐입니다.
\(j=1\)을 선택한다는 것은 \(3=1^2+(남은 값)\)의 형태라는 뜻입니다.
남은 값은 \(3-1=2\)입니다.
남은 값이 \(2\)라는 것은 \(j^2\) 하나만으로 \(i\)를 모두 설명할 수 없고, 남은 \(2\)를 더 표현해야 한다는 의미입니다.

원칙 3

남은 값 \(2\)의 최소 제곱수 개수는 이미 계산된 \(dp[2]=2\)입니다.
이 최소해에 마지막으로 선택한 \(j^2\) 하나를 더해 \(2+1=3\)입니다.

원칙 4

가능한 \(j\)는 \(1\) 하나뿐이므로 \(dp[3]=3\)로 업데이트됩니다.

✅ \(i=4\)

원칙 1

우리는 제곱수들의 합이 \(i=4\)이 되도록 만드는 최소한의 제곱수 개수를 구해야 합니다.
즉, \(4 = x_1^2 + x_2^2 + \dots\) 형태로 표현하면서, 사용되는 제곱수의 개수가 가장 적어야 합니다.
예를 들어, \(4=1+1+1+1\) 또는 \(4=2^2\)로 표현할 수 있습니다.

원칙 2

\(j\)는 마지막에 더한 제곱수의 밑을 의미합니다.
여기서 가능한 \(j\)는 \(1\)과 \(2\)입니다.

• \(j=1\)을 선택하면 \(4=1^2+(남은 값)\)입니다. 남은 값은 \(4-1=3\)입니다.
• \(j=2\)를 선택하면 \(4=2^2+(남은 값)\)입니다. 남은 값은 \(4-4=0\)입니다.

원칙 3

남은 값에 대한 최소 제곱수 개수를 확인합니다.

• \(j=1\)을 선택했을 때 남은 값 \(3\)의 최소해는 \(dp[3]=3\)입니다. 여기에 \(1\)을 더하면 \(4\)입니다.
• \(j=2\)를 선택했을 때 남은 값 \(0\)의 최소해는 \(dp[0]=0\)입니다. 여기에 \(1\)을 더하면 \(1\)입니다.

원칙 4

\(j=1\)과 \(j=2\)를 비교했을 때, \(j=2\)를 선택한 경우가 더 작습니다.
따라서 \(dp[4]=1\)로 업데이트됩니다.

✅ \(i=5\)

원칙 1

우리는 제곱수들의 합이 \(i=5\)이 되도록 만드는 최소한의 제곱수 개수를 구해야 합니다.
즉, \(5 = x_1^2 + x_2^2 + \dots\) 형태로 표현하면서, 사용되는 제곱수의 개수가 가장 적어야 합니다.
예를 들어, \(5=1+1+1+1+1\) 또는 \(5=4+1\)로 표현할 수 있습니다.

원칙 2

\(j\)는 마지막에 더한 제곱수의 밑을 의미합니다.
여기서 가능한 \(j\)는 \(1\)과 \(2\)입니다.

• \(j=1\)을 선택하면 \(5=1^2+(남은 값)\)입니다. 남은 값은 \(5-1=4\)입니다.
• \(j=2\)를 선택하면 \(5=2^2+(남은 값)\)입니다. 남은 값은 \(5-4=1\)입니다.

원칙 3

남은 값에 대한 최소 제곱수 개수를 확인합니다.

• \(j=1\)을 선택했을 때 남은 값 \(4\)의 최소해는 \(dp[4]=1\)입니다. 여기에 \(1\)을 더하면 \(2\)입니다.
• \(j=2\)를 선택했을 때 남은 값 \(1\)의 최소해는 \(dp[1]=1\)입니다. 여기에 \(1\)을 더하면 \(2\)입니다.

원칙 4

\(j=1\)과 \(j=2\)를 비교했을 때 둘 다 최소값이 \(2\)입니다.
따라서 \(dp[5]=2\)로 업데이트됩니다.

✅ \(i=6\)

원칙 1

우리는 제곱수들의 합이 \(i=6\)이 되도록 만드는 최소한의 제곱수 개수를 구해야 합니다.
즉, \(6 = x_1^2 + x_2^2 + \dots\) 형태로 표현하면서, 사용되는 제곱수의 개수가 가장 적어야 합니다.
예를 들어, \(6=1+1+1+1+1+1\) 또는 \(6=4+1+1\)로 표현할 수 있습니다.

원칙 2

\(j\)는 마지막에 더한 제곱수의 밑을 의미합니다.
여기서 가능한 \(j\)는 \(1\)과 \(2\)입니다.

• \(j=1\)을 선택하면 \(6=1^2+(남은 값)\)입니다. 남은 값은 \(6-1=5\)입니다.
• \(j=2\)를 선택하면 \(6=2^2+(남은 값)\)입니다. 남은 값은 \(6-4=2\)입니다.

원칙 3

남은 값에 대한 최소 제곱수 개수를 확인합니다.

• \(j=1\)을 선택했을 때 남은 값 \(5\)의 최소해는 \(dp[5]=2\)입니다. 여기에 \(1\)을 더하면 \(3\)입니다.
• \(j=2\)를 선택했을 때 남은 값 \(2\)의 최소해는 \(dp[2]=2\)입니다. 여기에 \(1\)을 더하면 \(3\)입니다.

원칙 4

\(j=1\)과 \(j=2\)를 비교했을 때 둘 다 최소값이 \(3\)입니다.
따라서 \(dp[6]=3\)로 업데이트됩니다.

✅ 전체 코드 Python

import sys

# PyPy3 환경에서 최적화된 입력을 위해 sys.stdin.readline 사용
input = sys.stdin.readline

n = int(input())
dp = [i for i in range(n + 1)]

# dp[i]는 숫자 i를 제곱수의 합으로 표현하는 최소 개수를 저장
for i in range(1, n + 1):
    # j는 제곱수의 밑이 되며, j*j가 i를 넘지 않는 범위까지 반복
    for j in range(1, int(i**0.5) + 1):
        # 현재 dp[i] 값과, (i - j*j)의 최소 개수에 1(j*j)을 더한 값을 비교하여 더 작은 값으로 갱신
        dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])

✅ 개별 코드

입력 및 변수 선언

import sys

# PyPy3 환경에서 최적화된 입력을 위해 sys.stdin.readline 사용
input = sys.stdin.readline

n = int(input())
dp = [i for i in range(n + 1)]

• 무엇을 하는지: `sys` 모듈을 임포트하고, `input` 함수를 `sys.stdin.readline`으로 재정의하여 입력 속도를 최적화합니다. 사용자로부터 정수 `n`을 입력받습니다.
• `dp` 리스트: `dp[i]`는 정수 `i`를 제곱수의 합으로 표현할 때 필요한 최소 항의 개수를 저장하는 리스트입니다. 리스트의 크기를 `n+1`까지 생성합니다.

초기화

dp = [i for i in range(n + 1)]

• 무엇을 하는지: `dp[i]`를 일단 `i`로 초기화합니다.
• 이유: 최악의 경우 \(1^2\)만을 사용해서 `i`를 만들 수 있기 때문입니다. 예를 들어, `3 = 1+1+1`로 최소 `3`개가 필요하므로 `dp[3]=3`으로 초기화됩니다.

동적 계획법 계산

for i in range(1, n + 1):
    for j in range(1, int(i**0.5) + 1):
        dp[i] = min(dp[i], dp[i - j * j] + 1)

• 바깥 반복문: `i`를 `1`부터 `n`까지 하나씩 탐색합니다.
  • 현재 `i`를 만드는 데 필요한 최소 제곱수 개수를 갱신합니다.
• 안쪽 반복문: `j`를 `1`부터 `j*j <= i`인 범위까지 증가시키며 확인합니다. `int(i**0.5)`는 `i`의 제곱근을 정수형으로 변환하여 `j`의 최대 범위를 효율적으로 설정합니다.
  • 현재 `i`를 표현할 때 마지막에 `j*j`를 사용했다고 가정합니다.
  • 그럼 나머지 `i - j*j`는 이미 최소 개수가 `dp[i - j*j]`로 계산되어 있습니다.
  • 거기에 `+1`을 해서 현재 `i`의 후보 값으로 갱신합니다.
  • 현재 저장된 값보다 더 작은 경우에만 갱신합니다.

출력

print(dp[n])

• 무엇을 하는지: `n`을 표현할 때 필요한 최소 제곱수 개수를 출력합니다.

✅ 결론

• 이 프로그램은 동적 계획법(DP)을 활용하여, 작은 수부터 차례로 최소 제곱수의 개수를 계산해 나갑니다.
• 각 `i`마다 \(1^2, 2^2, \dots\)를 마지막에 붙이는 경우를 모두 시도하며, 그중 최소를 선택합니다.
• 초기화는 최악의 경우 \(1^2\)만 사용했을 때의 개수로 설정하고, DP를 통해 더 나은 해를 찾아나갑니다.
• 최종적으로 `dp[n]`에 저장된 값이 `n`을 표현할 때 필요한 제곱수의 최소 개수가 됩니다.

• ✅ 작은 문제를 풀어 큰 문제를 푸는 하향식 사고를 연습할 수 있습니다.
• ✅ 제곱수를 마지막에 붙이는 방식으로 생각하여 문제를 단순화합니다.
• ✅ 동적 계획법을 통해 시간 복잡도를 \(O(N\sqrt{N})\)으로 줄입니다.
• ✅ 최악의 경우에도 넷 이하의 제곱수 합으로 표현된다는 라그랑주의 정리를 구현합니다.