백준 1699번 C++ 제곱수의 합

제곱수의 합

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

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

생각했던 과정

7의 제곱수의 합의 최소 개수를 구한다고 해보자.

7보다 작은 제곱수 중 가장 큰 것은 4이므로 7-4=3

그 다음 3보다 작은 제곱수를 찾아서 3-1=2

그 다음 2보다 작은 제곱수를 찾아서 2-1=1

1보다 작은 제곱수는 없으므로 1-1=0

따라서 7=2^2+1+1+1

답이 4라고 생각했다.

그러나 예제를 보고 이렇게 생각한다면 100% 틀린다.

게시판을 보면 12를 예로 드는데,

12의 경우 위에 써진 로직대로 풀면

12=3^2+1+1+1

답이 4이다.

그러나, 12=2^2+2^2+2^2로 나타낼 수 있기 때문에 답은 3이고 4는 틀린 답이다.

따라서 단순히 가장 큰 제곱수를 찾아서 빼는 것으로는 이 문제를 해결할 수 없는 것이다.

12의 경우에서 보았듯이, 12를 제곱수의 합으로 나타내는 방법에는 여러가지가 있다.

그러므로 N보다 작거나 같은 숫자들에 대해서 제곱수의 합의 최소 개수를 갱신해나가며 답을 구해줘야 하는 것이다.

처음에 최소 제곱수인 1로만 구성된 개수로 dp를 초기화해준다.

3까지는 1로만 이루어진 합이 최선이기 때문에 반복문은 N이 4이상일 때만 돌아가게 되어있다.

내가 했던 실수는 (i-jj)%jj==0을 조건문으로 껴넣은 것이었는데 그걸 삭제하고 min함수 부분의 인수를 고치니 해결되었다.

4 이상인 모든 i에 대해서 dp[i]와 dp[i-j*j]+1 중에 무엇이 최소값인지 매번 갱신해나간다.

여기에서 +1 해주는 이유는 i-jj의 상태에서 jj만큼 더해준 횟수(1회)가 더해지기 때문이다.

코드

#include <iostream>
#define MAX 100001
using namespace std;
int dp[MAX]={0};
int main() {
    int N;
    cin>>N;
    for(int i=0; i<=N; i++) {
        dp[i]=i;
    }
    for(int i=4; i<=N; i++) {
        for(int j=2; j<=i; j++) {
            int jj=j*j;
            if(jj>i) break;
            if(jj==N) { puts("1"); return 0; }
            dp[i]=min(dp[i], dp[i-jj]+1);
        }
    }
    cout<<dp[N];
    return 0;
}

반성

어제 너무 안 풀려서 비슷한 문제 코드 참고해서 풀려다가 두 번 틀리고 그냥 나 혼자서 풀어야겠다 싶었다.

그래서 아예 갈아엎고 다시 짰다

아직은 혼자 생각해도 되는 거 아닐까

스이타 캠퍼스에서 수업 끝나고 셔틀 버스 타고 오면서 조건문을 추가하면 안 됐었구나! 하는 생각이 들어서

집에 빨리 가고 싶다는 생각이 들었었다.

나는 왜 이렇게 멍청한 걸까 자책하면서 며칠 동안 우울했는데 한 문제라도 푸니까 날아가는 기분

그 동안 풀었던 것도 차차 올려야겠다

dp... 감 잡았다고 생각하면 아닌 거 같고 ㅠㅠ 아직 연습이 덜 되어서 그렇겠지

dp는 점화식 짜는 게 제일 중요하다고 한다

그 말이 무엇인지 점점 깨닫게 되는 것 같다