JArchive 프로그래밍 일기

문제

제곱수의 합 백준 1699번

리뷰

배열 D[i] 는 i를 제곱수의 합으로 표현했을 때 최소항의 개수를 저장한다.

기본적으로 D[i] 는 1의 제곱으로 i 개 더하면 i를 만들수 있다. D[i] = i

ex) D[1] = 1개, D[2] = 2개 ( 1^2 + 1^2 )

i를 제곱수로 표현할 때, 자신보다 작은 수의 제곱수들로만 구성되어 있다.

아래는 D[i] 의 최소항 개수를 1부터 5까지 구해본 것이다.

D[1] = 1개 ( 1^2)

D[2] = 1개 ( 2^2)

D[3] = 2개 ( 1^2 + 2^2)

D[4] =1개 ( 2^2 )

D[5] = 2개 ( 2^2 + 1^2 )

점화식은 다음과 같다.

for(i = 1; i <= n; i++){

    D[i] = i; // i를 1의 제곱의 합으로만 나타내면 항의 개수 i개  

    for(j = 1; j*j <= i; j++){  // i보다 작은 제곱수들 

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

    }
}

n = 5로 주어질 때, D[5] 를 구해보자.

기본적으로 D[5] 는 1의 제곱의 합으로만 나타내서 5개의 항으로 구성할 수 있다. D[5] = 5개

5 보다 작은 제곱수는 1과 2가 있다.

그래서 i보다 작은 제곱수들(1 , 2 )의 합으로 i를 표현할 수 있다.

그래서 D[5] 는 D[2] 값에 1을 더한 경우, D[1의 제곱] 값에 1을 더한 경우 로도 나타낼 수 있다.

D[5] = D[2] + 1

D[5] = D[1] + 1

이 중에서 가장 작은 값이 D[5] 에 들어가야 한다.

D[5] = min ( 5, D[2] + 1, D[1] + 1 )

코드

#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

// 1699번 제곱수의 합  

int D[100001]; 

int main(void){

     int n = 0 ;      
    int i, j = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++){

        D[i] = i; // i를 1의 제곱의 합으로만 나타내면 항의 개수 i개  

        for(j = 1; j*j <= i; j++){  // i보다 작은 제곱수들 

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

        }
    }

     printf("%d", D[n]);

    return 0;
}