[백준/C++] 17626 - Four Squares

풀이 시간: 02:17:06

시간 복잡도: O(n√n) -> n에 대하여 n 이하의 모든 제곱수에 대한 연산 수행

공간 복잡도: O(n) -> 크기 n인 배열 dp

참고

https://beginnerdeveloper-lit.tistory.com/55

https://hongjw1938.tistory.com/47

https://ip99202.github.io/posts/백준-17626-Four-Squares/=

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

문제 풀이

처음에는 동적 프로그래밍이라는 개념 자체를 생각하지 않고 일단 풀었다.

사실 동적 프로그래밍 개념을 모조리 까먹어서 일단 내가 할 수 있는 만큼 풀어보자는 생각이었다.

 

이 문제의 핵심은, 자연수 n이 주어졌을 때, n을 최소 개수의 제곱수의 합으로 나타내는 것이다.

 

그래서 처음 전제는 n과 가장 가까운 수(가장 큰 수)의 제곱을 먼저 차례대로 구해서 빼는 것이었다.

 

그렇게 도출된 코드는 다음과 같았다.

#include <iostream>
using namespace std;

int n, cnt = 0;

int topDown(int n)
{
   int i = n;
   while(n > -1){
      if (i == 0) break;
      if (sqrt(i) - (long long)(sqrt(i)) == 0) // n의 제곱근과 n의 제곱근의 정수부분의 값이 같으면
      {
         n = i = n - i; // n과 i에 모두 n - i 값을 저장
         cnt++; // 제곱근의 개수 카운트
      }
      else i--;
   }
   return cnt;
}

int main(void)
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin >> n; 
   cout << topDown(n) << "\n";
}

 

위와 같이 코드를 구현하고 예시 입력들을 모두 입력해봤는데, 어떤 것은 답이 맞고 어떤 것은 답이 틀리게 나왔다.

그래서 코드를 까보니, 본 코드에는 문제가 하나 있었다.

 

이 코드에서는 제곱근의 합의 "최소"의 개수를 찾을 수 없다는 것이었다.

 

즉, 처음 전제인 어떤 m을 제곱하여 n과 가장 가까운 수를 먼저 구하기가 잘못된 것이었다.

 

올바른 답: 11339 = 105^2 + ... -> 4개

내 코드의 답: 11339 = 106^2 + ... -> 5개

 

그래서 솔루션을 참고하여 button-up 방식으로 동적 프로그래밍을 사용해 다시 구현하였다.

 

먼저 합이 n이 되는 제곱수들의 최소 개수를 담는 배열 dp를 생성했다.

 

그리고 다음과 같이 배열 dp의 각 값을 해당 값으로 초기화 해주었다.

dp[i] = i

왜나하면, 각각의 수는 최소한 그 수만큼의 1의 제곱으로 표현될 수 있기 때문에 제곱수들의 개수의 최댓값을 담은 것이다.

 

그리고 현재 dp[i]에 있는 값과 비교하여 더 작은 값으로 설정해주는 방식을 구현하는데,

 

현재 dp[i] 값과, dp[i - j * j] + 1을 비교하여 더 작은 값을 가지고 있는 것이 최소의 개수이므로 그 값으로 dp[i]를 갱신해준다.

 

이때, dp[i - j * j] + 1인 이유는 현재 dp[i]에서 제곱수인 j * j를 뺀 해당 배열의 값(dp[i - j * j]: 그 값에 대하여 이전의 모든 제곱수들의 합의 개수가 저장되어 있는 값)을 조회하여 그 값을 가져오고, 추가로 현재 뺀 제곱수 j * j의 경우의 수를 하나 더해준 것이다.

전체 코드

#include <iostream>
using namespace std;

int n, dp[50001]; // 1 <= n <= 50000

int main(void)
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin >> n;

   for (int i = 1; i <= n; i++)
   {
      dp[i] = i; // 1부터 n까지의 수에 대해 dp 배열 초기화, 각 수는 최소한 그 수만큼의 1의 제곱으로 나타낼 수 있기 때문
      // 각 i에 대하여 가능한 모든 제곱수 j*j를 뺀 값에 대한 dp값(해당 값에서의 제곱수의 최소 개수) 조회
      for (int j = 1; j * j <= i; j++) // j가 1부터 j*j가 i보다 작거나 같을 때까지 반복
      {
         // 현재 dp[i]와 비교하여 더 작은 값으로 설정
         // "dp[i - j * j] + 1"에서 1을 더해주는 이유는 현재 뺀 제곱수(j*j)의 경우의 수를 하나 더해준 것
         dp[i] = min(dp[i], dp[i - j * j] + 1);
      }
   }
   // 합이 자연수 n과 같게 되는 제곱수들의 최소 개수 출력
   cout << dp[n] << "\n";
}

 

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

17626번: Four Squares