백준 1699번 [제곱수의 합](C++) -yes6686- 티스토리

백준 문제 풀이: 1699 (제곱수의 합)

---

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

문제 설명:

주어진 자연수 n을 제곱수의 합으로 나타낼 때, 필요한 제곱수 항의 최소 개수를 구하는 문제입니다. 예를 들어 n = 7이면 4 + 1 + 1 + 1 = 7로 최소 4개의 항이 필요합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    dp[1] = 1; // 1은 자기 자신이 제곱수이므로 1개

    // DP 배열 초기화
    for (int i = 2; i <= n; i++) {
        dp[i] = i; // 최악의 경우: 모두 1의 제곱으로 채우는 경우
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], 1 + dp[i - j * j]); // 제곱수 j*j를 사용했을 때 최소 개수 갱신
        }
    }

    cout << dp[n]; // n을 제곱수의 합으로 나타낼 때의 최소 개수 출력
}

---

코드 설명

• DP 배열 초기화: - dp[i]는 숫자 i를 제곱수의 합으로 표현할 때 필요한 최소 항의 개수를 저장합니다.
• 기본값 설정: - dp[i]는 초기에는 최악의 경우를 가정하고 i로 설정합니다. (모두 1의 제곱으로만 채우는 경우)
• 반복문을 통한 최소값 갱신: - j를 제곱수로 두고, dp[i]를 1 + dp[i - j^2]로 갱신합니다. - 이때 j^2 ≤ i가 성립해야 합니다.

---

시간 복잡도 분석

• 외부 반복문 i는 O(n)번 실행됩니다.
• 내부 반복문은 제곱수가 j^2 ≤ i일 때 실행되므로 최대 O(√n)입니다.
• 따라서 전체 시간 복잡도는 O(n √n)입니다.

---

입출력 예시

• 입력 예시:

  7

• 출력 예시:

  4

• 설명: 7 = 4 + 1 + 1 + 1로 최소 4개의 제곱수 항이 필요합니다.

---

결론

이 문제는 동적 프로그래밍(DP)을 활용해 각 숫자를 제곱수의 합으로 표현할 때 최소 항의 개수를 효율적으로 구하는 문제입니다. DP의 기본 아이디어는 작은 문제의 해를 이용해 큰 문제의 해를 구하는 것입니다. 시간 복잡도는 O(n √n)로 효율적으로 해결할 수 있습니다.