반응형
https://www.acmicpc.net/problem/17626
이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 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) |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 13335 트럭 C++ [컴공과고씨] (2) | 2022.04.21 |
---|---|
백준 2841 외계인의 기타 연주 c++ [컴공과고씨] (0) | 2022.04.18 |
백준 10799 쇠막대기 c++ [컴공과고씨] (0) | 2022.04.16 |
백준 9012 괄호 c++ [컴공과고씨] (0) | 2022.04.16 |
백준 1158 오세푸스 문제 c++ [컴공과고씨] (0) | 2022.04.14 |