[백준] 17626번 Four Squares C++ 풀이

---

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포 알고리즘

---

문제 설명

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

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

---

입력 설명

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

---

출력 설명

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

---

예제 입력

25

26

11339

34567

---

예제 출력

1

2

3

4

---

아이디어

모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현 가능하므로 최대 제곱수의 개수는 4개이다.

그러므로 첫 번째, 두 번째, 세 번째 제곱수에 해당하는 변수 3개를 선언하여 3중 for 문으로 완전 탐색을 진행하여 최소 개수를 탐색한다.

---

알고리즘

최대 제곱수가 4개이므로 3중 for문을 돌며 첫 번째, 두 번째, 세 번째 제곱수의 값의 합이 입력받은 n과 일치할 때만 최대 제곱수의 개수를 측정하여 최소 개수를 갱신한다.

만약 3중 for 문을 끝까지 돌았는데도 갱신이 안 된다면 최소 제곱수가 4개라는 의미이므로 4를 출력한다.

빠른 탐색 종료를 위해서 탐색 종료 조건을 부여한다.

 

1. 최소 제곱수의 개수가 1이라는 의미는 더이상의 탐색이 의미 없는 것이므로 모든 탐색을 종료하고 1을 출력한다.

 

2. 최소 제곱수의 개수가 2인 상태에서 2개의 변수가 모두 0이 아닌 다른 수가 들어있다면 탐색을 계속 진행해도

최소 제곱 수의 개수가 2개 이하로 나올 수 없으므로 해당 for 문을 break로 탈출한다.

 

3. 최소 제곱수의 개수가 3인 상태에서 3개의 변수가 모두 0이 아닌 다른 수가 들어있다면 탐색을 계속 진행해도 최소 제곱수의 개수가 3개 이하로 나올 수 없으므로 해당 for 문을 break로 탈출한다.

 

4. 현재 0이 아닌 변수들의 제곱의 합이 n보다 크다면 이후의 모든 탐색이 최소 제곱수의 개수를 갱신할 수 없으므로 continue 다음 for 문으로 진행한다.

---

코드

#include <iostream>
#include <cmath>
using namespace std;
int cal(int n)
{
    int min = 4;
    for(int a1 = sqrt(n); a1>=1; a1--)
        {
            if(min == 1) return min;
            int n2 = n - a1*a1;
            for(int a2 = sqrt(n2); a2>=0; a2--)
                {
                    if(min == 1) return min;
                    if(min == 2 && a2 != 0) break;
                    if(pow(a1,2)+pow(a2,2) > n) continue;
                    int n3 = n2 - a2*a2;
                    for(int a3 = sqrt(n3); a3>=0; a3--)
                        {
                            if(min == 1) return min;
                            if(min == 2 && a2 != 0) break;
                            if(min == 3 && a2 != 0 && a3 != 0) break;
                            if(pow(a1,2)+pow(a2,2)+pow(a3,2) > n) continue;
                            if(pow(a1,2)+pow(a2,2)+pow(a3,2) == n)
                            {
                                int cnt = 1;
                                if(a2 != 0) cnt++;
                                if(a3 != 0) cnt++;
                                if(min > cnt) min = cnt;
                            }
                        }
                }
        }
    return min;
}
int main() {
    int n;
    cin>>n;
    cout<<cal(n);
    return 0;
}

---

후기

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

처음에는 n의 제곱근에서부터 시작해서 무작정 빼는 식으로 하다가 실패했다.

두 번째로는 DP로 풀어보려다가 도저히 뭘 저장해야 할지 모르겠어서 실패했다.

그래서 브루트포스로 풀려고 시도하던 도중 변수가 3개만 있어도 충분하다는 힌트를 보고 3중 for 문을 사용한 브루트포스로 문제를 해결할 수 있었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!