[Algorithm/Kotlin] 백준 17626번 Four Squares: DP를 활용한 풀이법

문제 설명

1770년, 라그랑주는 모든 자연수는 네 개 혹은 그 이하의 제곱수 합으로 표현할 수 있다는 사실을 증명했습니다.

 

목표:

• 주어진 자연수 n을 최소 개수의 제곱수 합으로 표현하세요.

입력:

• 자연수 n (1 ≤ n ≤ 50,000)

출력:

• n을 표현할 수 있는 제곱수의 최소 개수

---

문제 해결 아이디어 

1. 접근 방법

처음에는 가장 큰 제곱수를 빼주면 되지 않을까? 하는 생각으로 그리디(Greedy) 접근법을 떠올렸습니다.

예: n = 12인 경우

• 가장 큰 제곱수인 9 (3²)를 선택
• 12 - 9 = 3 → 나머지 3을 다시 제곱수 합으로 표현: 1² + 1² + 1²
• 결과: 12 = 9 + 1 + 1 + 1 → 4개 사용

하지만, 더 나은 해가 존재합니다:

• 12 = 4 + 4 + 4 (2² + 2² + 2²) → 3개

1: 1      
2: 2
3: 3
4: 1     
5: 2
6: 3
7: 4
8: 2
9: 1     
10: 2
11: 3
12: 4 ❌ -> 3개 (2*2/2*2/2*2)
13: 2
14: 3
15: 4
16: 1

 

결론:

• 단순히 가장 큰 제곱수를 선택하는 그리디 방식으로는 최적해를 보장할 수 없습니다.
• 따라서, 모든 가능한 제곱수를 고려해야 하며, 이를 위해 동적 계획법(Dynamic Programming, DP)을 사용합니다.

2. 해결 아이디어

• 점화식:

dp[i] = min(dp[i], dp[i - j²] + 1)  (단, j² ≤ i)

 

• dp[i]는 정수 i를 표현할 때 필요한 최소 제곱수 개수
• j²는 i보다 작거나 같은 모든 제곱수
• 각 j²를 빼가며 최소값을 구합니다.
• dp[i]와 dp[i - j²] + 1을 비교하여, 항상 최소값을 유지해야 합니다.

---

구현 코드

import kotlin.math.min

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val dp = IntArray(n + 1) { it }  // 최악의 경우: 모두 1²로 표현

    dp[0] = 0  // 0을 표현하기 위한 제곱수는 없음

    for (i in 1..n) {
        var j = 1
        while (j * j <= i) {
            dp[i] = min(dp[i], dp[i - j * j] + 1)  // 최소 개수 갱신
            j++
        }
    }

    bw.write("${dp[n]}")
    bw.flush()
    bw.close()
}

---

사용한 자료구조

동적 계획법(DP) - Bottom-Up 방식

• DP 방식:
  • Bottom-Up(바텀업) 방식의 동적 계획법을 사용
  • 작은 문제부터 차례대로 해결해 나가며, 최종적으로 큰 문제(n)를 해결
  • 재귀 호출 없이 반복문을 통해 문제를 해결하며, 메모이제이션을 위해 배열을 사용
• 작은 문제부터 해결:
  • dp[1], dp[2], dp[3] 등 작은 값을 먼저 계산
  • 이를 통해 큰 값의 계산에 재활용
• 중복 계산 방지:
  • 이전에 계산된 dp[i - j²] 값을 활용하여,
  • 중복 계산을 피하고 빠르게 최적해를 찾음
• DP 배열 구조:
  • 목적:
    • 정수 i를 표현하는 데 필요한 최소 제곱수 개수를 저장
    • dp[i]는 정수 i를 제곱수 합으로 표현할 때 최소로 필요한 제곱수의 개수를 의미
  • 구조:
    • 1차원 정수 배열 dp
    • 크기: n + 1 (0부터 n까지 표현하기 위해)
    • 각 인덱스 i는 정수 i를 표현할 때 필요한 최소 제곱수 개수를 나타냄
• 초기화:
  • dp[0] = 0 → 0을 표현하는 데 필요한 제곱수는 없음
  • 나머지 값들은 최악의 경우를 가정하여 초기화
    • dp[i] = i로 설정
    • 이유: 최악의 경우, i를 1² + 1² + ... + 1² (총 i개)로 표현 가능
  예시:
  • dp[3] = 3 (초기값) → 3 = 1² + 1² + 1²
  • 이후, 더 나은 해를 찾을 경우 값을 업데이트
• 점화식:

dp[i] = min(dp[i], dp[i - j²] + 1)  (단, j² ≤ i)

 

• i를 표현할 때, j²를 뺀 나머지(i - j²)의 최소 개수에 +1을 추가
• 모든 j²에 대해 최소값을 갱신

Top-Down 방식과의 차이

• Top-Down (재귀 + 메모이제이션) 방식과는 달리,
  • Bottom-Up 방식은 재귀 호출이 없고,
  • 반복문을 통해 차례로 값을 계산
  • 스택 오버플로우 위험이 없고, 메모리 사용량도 예측 가능

---

시간 복잡도 분석

• 루프 구조
  • 외부 루프: for (i in 1..n) → O(n)
  • 내부 루프: while (j * j <= i) → 각 i에 대해 O(√i)
• 총 시간 복잡도
  • 최악의 경우:
    O(Σ√i) = O(n√n)

---

실행 결과 예시

• 입력: 12
  출력: 3 → (2² + 2² + 2²)
• 입력: 26
  출력: 2 → (5² + 1²)
• 입력: 11339
  출력: 4 → (105² + 15² + 8² + 5²)

---

정리

• 이 문제는, 그리디 방식으로는 항상 최적해를 찾을 수 없으므로, 동적 계획법(DP)을 사용하여 모든 가능한 제곱수를 고려해야 합니다.
• 사용한 DP 방식: Bottom-Up
• 메모이제이션 기법: 1차원 배열
• 점화식:

dp[i] = min(dp[i], dp[i - j²] + 1)  (단, j² ≤ i)

• 시간 복잡도: O(n√n)
• 공간 복잡도: O(n)

---

문제링크: https://www.acmicpc.net/problem/17626