https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다
www.acmicpc.net
풀이 :
간단한 문제자체는 간단한데 나만 어려웠나..? 생각보다 잘 안풀렸다. 솔루션 자체는 간단한데 생각보다 제곱수 빼고 하는 걸 구현하는데 삽질을 좀 했다. 해결하는 아이디어 자체는 조금 생각해보면 금방 떠올릴 수 있는 정도 내가 어려웠던 점은 반복문 한번으로 구할 수 있을 것 같아서 고민하다가 결국 솔루션을 봤는데 이중 반복문으로 j * j <= i 이런식으로 제곱수의 근사값까지 계산하는 걸 생각못했다.. 솔루션을 좀 풀어서 설명해보자면
dp[n] = a 일때 숫자 n을 제곱수의 합으로 나타낼 때 제곱항의 최소숫자를 a로 생각한다.
dp[1]은 당연히 1이고
dp[2] = 2 (1의 제곱 2개)
dp[3] = 3 (1의 제곱 3개)
dp[4] 부터는 제곱수를 고려해줘야 한다. 2의 제곱 은 4이기 때문에 dp[4] =1
dp[5]=2 인데 제곱수인 4 + 1 = 5 이기 때문
즉, n보다 작은 제곱수의 근사값을 고려해줘야 한다. 반복문 돌면서 dp[i - j*j]+1 하면 되는데 좀 더 큰 수로 예를 들자면
16 같은 경우는 내부 반복문의 j 가 1, 2, 3, 4 이렇게 네번 돌면서 이전에 저장해온 dp 값을 계속 비교하며 최소값을 저장해주면 됨
코드 :
#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001];
int N;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
dp[i] = i;
for (int j = 1; j *j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[N] << endl;
}
'baekjoon' 카테고리의 다른 글
[DP] 백준 9251 LCS C++ (0) | 2022.02.15 |
---|---|
[DFS]백준 2644 촌수계산 C++ (0) | 2022.02.06 |
[DP] 백준 2294 동전2 C++ (0) | 2022.01.25 |
[문자열] 백준 5430 AC C++ (0) | 2022.01.24 |
[그리디] 백준 4796 캠핑 C++ (0) | 2021.09.02 |
댓글