백준 17626번 [Four Squares](C++) -yes6686- 티스토리

백준 문제 풀이: 17626 [Four Squares]

---

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

문제 설명:

주어진 자연수 n을 네 개 이하의 제곱수의 합으로 표현할 때, 필요한 제곱수의 최소 개수를 구하는 문제입니다. 예를 들어, n = 7일 때, 4 + 1 + 1 + 1로 표현할 수 있으므로 답은 4입니다.

입력:

• 첫째 줄에 자연수 n이 주어집니다. (1 ≤ n ≤ 50,000)

출력:

• n을 네 개 이하의 제곱수의 합으로 표현할 때 필요한 제곱수의 최소 개수를 출력합니다.

예시:

입력:
7

출력:
4

---

문제 해결 코드

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

int dp[50001]; // dp[i]: i를 표현하는 데 필요한 최소 제곱수의 개수

int main() {
    int n;
    cin >> n;

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = i; // 최악의 경우, 모두 1의 제곱수로 표현 (1 + 1 + ... + 1)
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1); // i에서 j^2을 빼고 필요한 최소 개수 + 1
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

---

코드 설명

이 코드는 동적 프로그래밍(DP)을 사용하여 자연수 n을 표현하는 데 필요한 최소 제곱수의 개수를 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 동적 프로그래밍을 사용하여 작은 문제를 해결하면서 큰 문제를 해결합니다.
  • 점화식: dp[i] = min(dp[i], dp[i - j^2] + 1)
  • 점화식 유도:
    • j^2는 사용할 수 있는 제곱수입니다.
    • dp[i - j^2]는 i - j^2를 표현하는 최소 제곱수의 개수입니다.
• 구현 세부사항:
  • dp[i]를 i를 표현하는 데 필요한 최소 제곱수의 개수로 정의합니다.
  • 1부터 n까지 모든 수에 대해 필요한 최소 개수를 계산합니다.
• 시간 복잡도 분석:
  • 외부 반복문: O(n)
  • 내부 반복문(최대 루트 n까지): O(sqrt(n))
  • 총 시간 복잡도: O(n * sqrt(n))

---

결과

코드는 입력된 자연수 n을 네 개 이하의 제곱수로 표현하는 데 필요한 최소 개수를 효율적으로 계산합니다. 동적 프로그래밍을 활용하여 O(n * sqrt(n))의 시간 복잡도로 문제를 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!