Game Develop

[Algorithm] Baekjoon 17626번 : Four Squares 본문

Algorithm/Baekjoon

[Algorithm] Baekjoon 17626번 : Four Squares

MaxLevel 2022. 10. 25. 00:52

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

 

17626번: Four Squares

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

www.acmicpc.net

 
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
int dp[50001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    dp[1= 1;
 
    cin >> n;
 
    for (int i = 1; i * i <= n; i++)
    {
        dp[i * i] = 1;
    }
    
    for (int i = 1; i <= n; i++
    {
        if (dp[i] != 1)
        {
            dp[i] = dp[i - 1+ 1;
            for (int j = 1; j * j <= i; j++)
            {
                dp[i] = min(dp[i], dp[j * j] + dp[i - j * j]);
            }
        }
    }
    
    cout << dp[n];
    
    return 0;
}
cs

DP문제가 으레 그렇듯이, 특정한 규칙을 잘 찾냐 못찾냐에 따라 푸는시간이 달라지는 문제..

특정 수 n을 제곱의 합이 될 수 있는 경우의 수는 아래와 같다.

n == 10일 경우,

dp[1] + dp[9],

dp[2] + dp[8] ,

dp[3] + dp[7] ........ 이중에서 최솟값..

 

여기서 중요한 점은, n 이하의 i가 제곱수일 경우, dp[i] = 1이다. 즉, dp[25] = 1, dp[36] = 1....

해당 수를 만들기 위한 수행수는 제곱한번이기 때문이다.

그렇기 때문에 위와 같은 제곱수들을 이용하면 최소의 값을 구할 경우의 수를 좀 더 줄여서 표현가능하다.

 

그러기 위해 미리 루트n까지의 dp[i*i]를 미리 1로 세팅한다.

그리고 위의 코드처럼 Bottom->Top형식으로 dp테이블을 업데이트 시켜주면 된다.

 

반복문을 돌릴 때 sqrt를 사용하는것보다 위처럼 j*j <= i 이런식으로 해주는게 좋다.

수행속도가 상당히 많이 차이난다. sqrt를 사용했을때 32ms가 나왔었는데 j*j <= i형식으로 해주면 16ms가 나왔다.

2배가 차이난다는 뜻.

원래 제곱근 구하는 함수는 성능이 좋지 않다. 값을 구하기까지 나누고 곱하고.. 무수히 많은 연산을 한다.

제곱근 구하는 함수코드를 보면, 굳이 이런문제에서 사용할 필요가 없다는 것을 알 수 있다.

 

이미 dp[i]가 1이면 그것보다 더 낮은 값이 나올 수 없으니 반복문을 수행하지 않는다. 

마찬가지로 하나 안하나 성공은 하나, 16ms -> 12ms로 약 1.33배의 성능차이가 있다.