[BOJ/백준][Silver5] 17626 : Four Squares (C++)

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

17626번: Four Squares

 

 

[난이도] Silver5
[유형] DP

[풀이]
set a[3] 과 같이 선언하여
a[1]에는 1개의 제곱수로 만들 수 있는 숫자들,
a[2]에는 2개의 제곱수를 만들 수 있는 숫자들을 저장합니다.
set을 사용한 이유는 1^2+2^2, 2^2+1^2 등 중복되는 경우가 저장될 수 있기 때문입니다.
a[2]는 a[1]의 원소들로 2중 for문으로 구할 수 있으며
중간에 n과 동일한 수가 나오면 제곱수의 개수를 return 해줍니다.

a[1],a[2]를 구해놨으면 3개와 4개의 제곱수로 만들어진 n도 한번에 구할 수 있습니다.

3개로 만들 수 있는 제곱수는 모든 a[1]을 순회하면서 현재 나온 수가 v일때,
a[2]에 n-v가 있다면 제곱수 3개로 n을 만들 수 있다는 의미이므로 3을 return 해줍니다.

4일때도 마찬가지로
a[2]를 순회하면서 현재 나온 수가 v일때 a[2]에 n-v가 있다면 제곱수 4개로 n을 만들 수 있다는 의미이므로
4를 return 해주면 됩니다.

 

 

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
int n;
set<int> a[3];
int sol(){
    for(int i=1;i<=sqrt(n);i++){
        if(i*i==n) return 1;
        a[1].insert(i*i);
    }
    for(auto v1 : a[1]){
        for(auto v2 : a[1]){
            if(v1+v2==n) return 2;
            a[2].insert(v1+v2);
        }
    }    
    for(int i=1;i<3;i++){
        for(auto v : a[i]){
            if(a[2].find(n-v) != a[2].end()) return i+2;
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    printf("%d",sol());
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver5/17626.cpp