[BaekJoon] 1699. 제곱수의 합

1699. 제곱수의 합

 

 

우선 DP[] 배열을 전부 i값으로, 즉 제곱수가 전부 1로 구성되는 경우로 초기화한다

이처럼 DP[i]가 가질 수 있는 max값으로 설정해 두면,

    for(i=1;i<=cnt;i++)
        DP[i]=i;

 

우리는 이제 n의 크기 내에서 표현할 수 있는 제곱수들 1*1, 2*2, ... j*j를 이용하여 최소의 방법으로 DP를 갱신해야 한다.

 

11을 예시로 들어보자. 11의 범위 내에서 표현할 수 있는 제곱수들은 1,4,9이고, 우리는 이들을 조합하여 최소 항의 갯수를 구해내야 한다.

11에서 이 제곱수들을 빼가며, 세 가지 경우 중 어떤 경우가 최솟값을 가지는지 알아내는 과정을 반복하면 될 것이다.

DP[11]의 경우라면, min(DP[11-(1*1)]+1,DP[11-(2*2)]+1,DP[11-(3*3)]+1중 최솟값을 가지게 되겠지?

 

따라서 i보다 작거나 같은 범위에 있는 제곱수들에 대한 for문을 수행,

제곱값을 빼준 index의 DP값에 1을 더한 값과, 기존에 DP에 저장되어 있던 값과 비교하여, 더 작은 값으로 갱신한다.

(1을 더하는 이유는, 완전 제곱수의 최소항이 1이기 때문이다: DP[1*1]=DP[2*2]=...=DP[j*j]=1)

    for(i=2;i<=cnt;i++){
        for(j=2;j*j<=i;j++){
            DP[i]=minValue(DP[i-(j*j)]+1,DP[i]);
        }
    }

 

전체 코드이다.

#include <stdio.h>
#include <stdlib.h>

int DP[100001];
int minValue(int a,int b){return a<b? a: b;}
int main(){
    
    int i,j,cnt;
    scanf("%d",&cnt);
    for(i=1;i<=cnt;i++)
        DP[i]=i;
    
    for(i=2;i<=cnt;i++){
        for(j=2;j*j<=i;j++){
            DP[i]=minValue(DP[i-(j*j)]+1,DP[i]);
        }
    }
    printf("%d\n",DP[cnt]);
    
    return 0;
}

---

 

나는 이 문제를 단순한 dynamic programming문제라고만 생각하였는데, 이 문제를 푸는 원리는 사실상 knapsack 알고리즘의 원리였다.

제한된 최대 용량 내에서(N의 범위), 최대의 가치를(최소항) 창출해내는 개념이니까.

가방 문제에 11을 예시로 들어서 적용해보면,

11kg의 책을 담을 수 있는 가방이 있고,

책들은 반드시 11보다 작거나 같은 수들 중, 제곱인 값의 무게를 가진다 (1kg, 4kg, 9kg)

가방에 정확히 무게의 합이 11kg가 되도록 책을 담는다고 할 때, 책의 권 수가 최소가 되도록 담는 경우를 구해내면 되는 것이다.

 

내일은 knapsack 문제 풀어야겠다.

개념만 알지, 막상 구현해보려니까 머리가 백지가 되더라...