[BOJ] 1699. 제곱수의 합
문제
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
출력
주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.
예제 입력 1
7
예제 출력 1
4
접근 방식
DP 문제다. 전에 저장되어있던 수의 최소 개수를 이용해야 되는 것은 알겠는데 점화식을 세우지 못했다. DP는 점화식이 가장 중요하다는데 .. 아직 연습이 많이 필요하다.처음에는 i 부터 n 까지 반복문 안에서 dp[i] = dp[i-1]+1 을 넣어두고 i보다 작은 가장 큰 j*j를 i 에서 빼면서 카운트를 세는 방식으로 풀었는데 1이 아닌 다른 제곱수로만 구성된 수들이 고려 되지 않았다. 접근법이 잘못 된 것을 깨달았다.
다른 분들이 올려주신 글을 보고 깨달은 원리는 dp[i]와 dp[i-4], dp[i-9] ... 와 같은 값들과 비교해야 한다는 것이다. -4,-9 .. 는 제곱수로 저만큼을 뺀 수의 dp 값에 +1 (- 제곱수 했기 때문에 ) 한 값과 비교했을 때의 최소값을 찾아야 한다.
dp[i] = min(dp[i], dp[i-j*j]+1)
이 원리를 보고 문제 풀이에 도전했는데, 당연히 j는 i의 제곱근 이면 될 줄 알았는데 아무리 풀어도 '틀렸습니다'만 나왔다. 질문글을 찾아보다가 예외를 발견했다.
12가 그 예외인데 내가 푼 방식대로면.
12 - min(dp[i], dp[12-3*3]+1) , dp[3] + 1 => 4
하지만 답은
12 - 2*2 + 2*2 + 2*2 =>3
따라서 제곱근과만 비교해서는 최소값을 찾을 수 없다. 제곱근까지의 제곱수들을 i에서 뺀 dp 값들과 모두 비교해줘야 한다.
코드
#include<iostream>
#include <math.h>
using namespace std;
int dp[100001]={0,};
int arr[100001]={0,};
int main(){
int n,j;
cin>>n;
//최소 제곱수 1로만 구성된 개수로 dp 초기화
for(int i=1;i<=n;i++)
dp[i]=i;
for(int i=4;i<=n;i++){
for(int j=sqrt(i);j>0;j--){
if(j*j==i){
dp[i]=1; break;
}
dp[i] = min(dp[i],dp[i-j*j]+1);
}
}
cout<<dp[n];
}
| cs |
No comments: