일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 2294
- 언리얼엔진5
- algorithm
- 티스토리챌린지
- UnrealEngine5
- softeer
- 1563
- baekjoon
- C
- DirectX11
- 줄 세우기
- C++
- 팰린드롬 만들기
- 백준
- DeferredRendering
- GeeksForGeeks
- RVO
- const
- winapi
- RootMotion
- directx
- Frustum
- 프로그래머스
- Programmers
- Unreal Engine5
- IFileDialog
- NRVO
- 오블완
- UE5
- UnrealEngine4
- Today
- Total
Game Develop
[Algorithm] Baekjoon 17626번 : Four Squares 본문
https://www.acmicpc.net/problem/17626
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배의 성능차이가 있다.
'Algorithm > Baekjoon' 카테고리의 다른 글
[Algorithm] Baekjoon 9019번 : DSLR (0) | 2022.10.26 |
---|---|
[Algorithm] Baekjoon 1074번 : Z (0) | 2022.10.25 |
[Algorithm] Baekjoon 14500번 : 테트로미노 (0) | 2022.10.21 |
[Algorithm] Baekjoon 16236번 : 아기상어 (0) | 2022.10.21 |
[Algorithm] Baekjoon 7662번 : 이중 우선순위 큐 (0) | 2022.10.21 |