백준 1699번 제곱수의 합

문제 링크입니다: 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을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

 

const int INF = 987654321;

const long long MAX = 100000 + 1;

long long cache[MAX];

long long N; //주어진 자연수

 

void preCalculate(void) //미리 계산

{

        for (int i = 1; i * i <= N; i++)

               cache[i] = i*i;

}

 

long long minSquare(void)

{

        long long result = INF, temp = N;

        for (long long i = (long long)sqrt(temp); i >= 1; i--)

        {

               long long sum = 0;

               for (long long j = i; temp && j >= 1; j--)

               {

                       sum += temp / cache[j];

                       temp %= cache[j];

               }

               result = min(result, sum);

               temp = N;

        }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N >= MAX)

               exit(-1);

        preCalculate();

        cout << minSquare() << endl;

        return 0;

}

위 코드의 문제점은 항상 큰 제곱수부터 더해나간다는 것이였습니다.

예를 들어 43은 25+9+9로 최소항 개수가 3입니다. 하지만 위 코드에서는 큰 제곱수부터 더해나가기 때문에 36+4+1+1+1로 최소항 개수를 5라고 단정짓습니다.

그래서 메모이제이션을 이용하여 N보다 밑에 있는 모든 제곱수를 더해나가며 최소 항 개수를 아래와 같이 찾아봤습니다.

/*

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.

예를 들어 11=32+12+12(3개 항)이다.

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

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

*/

#include <iostream>

#include <cstring> //memset

#include <cmath>

using namespace std;

 

const int INF = 987654321;

const int MAX = 100000 + 1;

int cache[MAX];

int N; //주어진 자연수

 

void preCalculate(void) //미리 계산

{

        memset(cache, 0, sizeof(cache));

        for (int i = 1; i * i <= N; i++)

               cache[i*i] = 1;

}

 

long long minSquare(void)

{

        for (int i = 2; i < MAX; i++)

        {

               if (cache[i] == 1) //이미 제곱수에 대해선 cache 계산했으므로

                       continue;

               int result = INF;

               for (int j = (int)sqrt(i); j >= 1; j--)

               {

                       int cnt = 1 + cache[i - (j*j)];

                       if (result > cnt) //최솟값을 갱신

                       {

                              result = cnt;

                              cache[i] = result;

                       }

               }

        }

        return cache[N];

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N >= MAX)

               exit(-1);

        preCalculate();

        cout << minSquare() << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~