[백준] 1699번. 제곱수의 합
1. 문제
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
3. 출력
주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.
4. 풀이
- 배열을 만들고 제곱수는 모두 값을 1로 초기화한다.
- 해당 수를 만들 수 있는 최소 경우의 수를 찾는다. (d[n] = min(d[n-1] + d[1], d[n-4] + d[4], d[n-3] + d[3]......)
5. 처음 코드와 달라진 점
- 젤 처음에는 제곱 수인지 찾는 함수를 구현하여
loop가 돌 때마다 제곱 수인지 확인했다. - 저번 문제 풀 때는
j<=i/2까지loop를 돌려놓고 멍청하게j<i-1까지loop를 돌렸다. - 기본 로직은 크게 다르지 않았는데 시간 초과가 나서 조금씩 바꾸니까
굉장히 느리게통과했다.
6. 코드
#include <iostream>
using namespace std;
int d[100001] = { 0, };
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 1; i * i <= n; i++) {
d[i * i] = 1;
}
d[2] = 2;
for (int i = 3; i <= n; i++) {
if (d[i] == 1) continue;
d[i] = d[i - 1] + 1;
for (int j = 2; j <= i / 2; j++) {
int value = d[i - j] + d[j];
if (d[i] > value) d[i] = value;
}
}
cout << d[n];
}