알고리즘 문제
[C/C++ 백준 1699번] 제곱수의 합 (Silver 3)
새파란 공대생
2020. 5. 5. 23:15
https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는
www.acmicpc.net
문제를 보고 고민도 안하고 바로 쓴 코드.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <cstdio>
#include <cmath>
using namespace std;
int main(void){
int N,n,cnt=0;
scanf("%d",&N);
while(N){
n = (int)sqrt((double)N);
N = N - n*n;
cnt++;
}
printf("%d",cnt);
}
|
? 틀렸다. 반례가 존재한다. 12의 경우, 2의 제곱인 4를 3번 더하면 답이 3이다.
그래서 생각난 아이디어가, n의 제곱수들의 합의 항의 개수를 N[n]이라 할때, N[n]=min(N[n-1]+1, N[n-4]+1, ...)로 하는 방법이다. N√N번 계산하는 거라 긴가민가 했지만, 일단 짜보았다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void){
int N[100001]={1,},n;
scanf("%d",&n);
for(int i=1; i<=n; i++){
int min=100001;
int j=1;
while(i-j*j>=0){
if(i==j*j)
min=1;
if(min>N[i-j*j]+1)
min=N[i-j*j]+1;
j++;
}
N[i]=min;
}
printf("%d",N[n]);
}
|
해결. 하지만 가동성면에서 아직 매우 떨어지는 거 같다. 열심히 해야겠다.