[Python][C++] 17626번 Four Squares

문제

https://www.acmicpc.net/problem/17626

 

 

 

 

코드

1. Python

import math

n = int(input())  # 입력으로 숫자 n을 받음
dp = [0] * (n + 1)  # DP 테이블 초기화 (0부터 n까지)
dp[1] = 1  # 1은 제곱수 1로만 표현 가능하므로 dp[1] = 1

# 2부터 n까지 최소 제곱수의 합을 찾기 위한 반복문
for i in range(2, n + 1):
    min_value = 1e9  # 임의로 큰 값으로 초기화 (최솟값을 찾기 위해)
    
    # i보다 작은 제곱수들을 탐색하며 최소 값을 찾음
    for j in range(1, int(math.sqrt(i)) + 1):
        min_value = min(min_value, dp[i - j ** 2])  # dp[i - j^2]의 최솟값을 갱신
    
    dp[i] = min_value + 1  # i를 제곱수들의 합으로 표현한 최소 개수를 저장

# 결과 출력 (n을 제곱수의 합으로 표현한 최소 개수)
print(dp[n])

 

2. C++

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

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

    vector<int> dp(n+1);

    for (int i = 1; i <= n; i++) {
        dp[i] = i;
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }

    cout << dp[n];

    return 0;
}

 

 

풀이

 

1. 제곱수 표현:
   • 어떤 자연수 n을 네 개 이하의 제곱수 합으로 나타낼 수 있다. 즉, n = a^2 + b^2 + c^2 + d^2와 같이 표현할 수 있으며, 최소 몇 개의 제곱수로 표현할 수 있는지를 구하는 문제이다.
2. 다이나믹 프로그래밍(DP) 사용:
   • dp[i]를 숫자 iii를 최소 몇 개의 제곱수 합으로 표현할 수 있는지 저장하는 배열로 설정한다.
   • 초기값으로 dp[0]=0을 설정하고, 이후 숫자 iii에 대해 1부터 iii까지의 제곱수를 확인하면서 최소 값을 갱신해 나간다.
   • 점화식: dp[i]=min⁡(dp[i],dp[i−j^2]+1)
3. 최적화:
   • 주어진 수 n에 대해 가능한 제곱수를 모두 탐색하면서, 각 숫자에 대해 제곱수의 합을 찾는다.