백준 17626 Four Squares C++ [컴공과고씨]

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

17626번: Four Squares

이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 n이 되도록 찾는 식으로 풀어 주었다. 

배열에 저장하지 않고 연산을 계속하면서 찾을 경우 당연히 연산 시간이 오래걸려 시간초과가 난다.

합이 n이 되도록 할 때 최소 개수의 수로 만들어야 함에 주의하도록 하자.

 

단계별 풀이

1. dp배열에 n보다 작거나 같은 제곱수까지 구해줌.

2. 가장 큰 제곱수가 n일 경우 1을 출력

3. for문을 돌며 2개의 수로 n이되면 2출력

4. 3개의 수로 n이되면 3을 ans에 저장 (2개의 수로 만들어 질 수 있기 때문에 일단 저장만)

5. 4개의 수로 n이되면 기존 ans와 비교하여 4를 저장 (2, 3개의 수로 만들어 질 수 있기 때문에 일단 저장만)

 

 

전체코드

#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a = 1;
    int ans = 5;
    int dp[50001];
    dp[0] = 1;
    dp[1] = 4;
    while(dp[a]<=n){ // n보다 작은 제곱수들 배열에 저장
        a++;
        dp[a] = a*a;        
    }
    if(dp[a-1] == n){ // 제일 큰 제곱수가 n과 같음
        cout << 1;
        return 0;
    }
    for (int i = 0; i < a; i++){
        for (int j = i; j < a; j++){
            if(dp[i] + dp[j] == n){
                cout << 2;
                return 0;
            }
            for (int k = j; k < a; k++){
                if(dp[i]+dp[j]+dp[k] == n){
                    ans = 3;
                }
                for (int z = k; z < a; z++){
                    if(dp[i]+dp[j]+dp[k]+dp[z] == n){
                        if(ans > 4){
                            ans = 4;
                        }
                    }
                }
            }
        }
    }
    cout << ans;
     return 0;
} //32min

체감 난이도	걸린시간	참고	사용 알고리즘
중하	38min	x	다이나믹 프로그래밍 (dynamic programming) 브루트 포스(brute force)