알고리즘/백준

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

시간빌게이츠 2022. 4. 16. 14:44
반응형

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

 

17626번: Four Squares

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1

www.acmicpc.net

이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 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개의 수로 만들어 질 수 있기 때문에 일단 저장만)

 

 

전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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
cs

 

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

브루트 포스(brute force)
반응형