코딩테스트

[백준] 17626번 Four Squares

스키(ski) 2022. 8. 30. 16:39
문제 내용

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
35
36
37
38
39
40
41
42
43
44
45
46
#include <cmath>//sqrt를 사용하기 위한 header
#include <iostream>
 
#define MAX_N 50001
 
using namespace std;
 
int dp[MAX_N];
int ans = 5;
 
void initialize() { //제곱수 초기화
    int n = 1;
    while (n * n <= 50000) {
        dp[n * n] = 1;
        n++;
    }
}
 
int find(int n) {
    if (!dp[n]) {
        int min = 4; 
        int s = sqrt(n); //가장 가까운 제곱을 확인하기 위함 ex)26=5.xxx->5
 
        for (int i = s; i > 0; i--) { //brute force부분
            int search = find(n - (i * i)); //제곱을 뺀 나머지를 탐색
 
            if (search < min) {//그중 최소가 되는값을 저장
                min = search;
            }
        }
 
        dp[n] = min + 1; // dp[n-i*i]+(dp[i*i]=1)
    }
    return dp[n];
}
 
int main() {
    int n;
 
    cin >> n;
 
    initialize();
 
    cout << find(n);
}
 
 cs

 

 
주요 개념 
  • 동적 프로그래밍 (Dynamic Programming,DP)
  • 브루트포스 알고리즘(Brute force)

 

주의 사항
  1. 시간 제한이 0.5초 이기에 이에 유의해야함, 하지만 0<=n<=50000이라는 조건에 의해 탐색범위가 넓지않음