BOJ 17626 Four Squares

 

문제 링크 : https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

탑다운, 바텀업 모두를 빠르게 작성하는 연습.

 

자연수 i 를 제곱수들의 합으로 표현할 때 필요한 제곱수의 개수를 최소화하라는 문제이니, 이를 dp[i] 라 두자.

i 이하의 수에 대해서 최소화된 개수를 모두 알고 있다면 다음이 성립한다.

$$ dp[i]= \min\limits_{j^2 \le i}  dp[i-j^2] +1$$

 

1. Bottom-UP

두 가지 바텀업 구현을 살펴본다.

dp[0]=0, 그 외의 값들은 매우 큰 값으로 초기화하는 것은 당연.

 

주어진 i 에서 더 큰 값들을 채워나가는 방식의 바텀업 구현부터.

 

#include<bits/stdc++.h>

using namespace std;

int dp[50001];

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) dp[i]=INT_MAX;
    
    for(int i=0;i<=n;i++){
        for(int j=1;i+j*j<=n;j++){
            dp[i+j*j]=min(dp[i+j*j], dp[i]+1);
        }
    }
    printf("%d\n", dp[n]);
}

 

주어진 i 를 앞에서 얻은 것들의 결과로 구현하는 방식은 다음과 같다.

 

#include<bits/stdc++.h>

using namespace std;

int dp[50001];

int main(){
    int n; scanf("%d",&n);
    
    for(int i=1;i<=n;i++){
        dp[i]=1e9;
        for(int j=1;j*j<=i;j++){
            dp[i]=min(dp[i], dp[i-j*j]+1);
        }
    }
    printf("%d\n", dp[n]);
}

 

2. Top-Down

base case 만 처리를 잘하면 된다.

 

#include<bits/stdc++.h>

using namespace std;

int dp[50001];

int recur(int n){
    if(n==0) return 0;
    
    int &ret=dp[n];
    if(ret) return ret;
    
    ret=INT_MAX;
    for(int i=1;i*i<=n;i++)
        ret=min(ret, recur(n-i*i)+1);
    
    return ret;
}

int main(){
    int n; scanf("%d",&n);
    printf("%d\n", recur(n));
}