[1699] 제곱수의 합, c++

1. 제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

한줄 후기 : 난 아직도 쪼렙이다.

---

이거 작년 icpc 인가 문제로 나왔던 거 같은데 그때 dp공포증 심해서 지혜가 풀었던 것 같음 다시 푸니까 풀리네 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

실버 3 난이도 이지만 나같은 쪼렙은 어렵다고요;

음~ 문제는 엄청 쉬워보임

그냥 n이라는 자연수를 제곱수들의 합으로 나타냈을 때 가장 작은 항 개수로 만들어 주면 됨.

즉, 7은 1+1+1+4 => 4개

32는 여러개 가능함 제일 적은 건 16+16 => 2개, 4+4+4+4+4+4+4+4 8개도 가능하지만 2개가 더 적잖아~

무튼 이런 식으로 풀면 된다.

 

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main(){
    int n, m;
    int dp[100001] = {0};
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    scanf("%d", &n);
    for(int i=4; i<=n; i++){
        m = sqrt(i);
        dp[i] = i;
        if(m*m == i)    dp[i] = 1;
        for(int j=1; j<=m; j++){
            dp[i] = min(dp[i], dp[j*j]+dp[i-(j*j)]);
        }
    }
    cout << dp[n];
}

자자 여기서 제일 많이 하는 실수 (It's me ;;)

1. 그냥 n이랑 가장 가까운 제곱수만 생각한다.

-> 틀림

ex) 163 일 경우 144+16+1+1+1 => 5개 ;;

정답은 163 = 81+81+1 => 3개 이다.

2. 그럼 그 제곱수에서 하나 더 작은 제곱수 까지 비교하자

-> 틀림 당장 작은 n일때는 맞겠지만 n이 커질 수록 다른 경우가 생김

​

포인트는 가장 가까운 제곱수를 사용하지 않고 더 작은 제곱수를 사용했을 때 더 적을 수 있다.

​

그래서 for문을 이중으로 돌리는 거다!!

for(int j=1; j<=m; j++){

dp[i] = min(dp[i], dp[j*j]+dp[i-(j*j)]);

}

보면 m은 sqrt(i) 즉 루트 i이고 (가장 가까운 제곱수)

안에서 j가 m일때까지 1부터 하나씩 증가시키면서 더 작은 항 개수를 dp[i]에 저장해주면 됨. 초기 dp[i]는 임의로 i로 저장해준다.

**만약 i가 제곱수면 그냥 1로 저장해주면 됨!!

뭔가 작년에 못풀었는데 지금 푸는거 보니 뿌듯하다. 

 

이 글 네이버에 쓴게 작년인데 뭔가 지금 더 퇴화된듯