[백준 17626번] Four Squares (C++)

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

17626번: Four Squares

---

Four Squares는 백트래킹과 메모이제이션을 이용하여 해결할 수 있습니다. 

N이 주어졌을 때 제곱수의 합으로 표현할 수 있는 숫자의 범위는 1부터 √N까지 입니다.

따라서 해당 범위에서 숫자를 선택하고, 재귀 함수의 파라미터로 선택한 숫자의 제곱을 뺀 값을 전달해주면 됩니다.

또한 이미 계산한 값을 배열에 저장함으로써 시간을 단축시킬 수 있습니다. 

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int m[500001];  // 메모이제이션을 위한 배열

int recur(int n){
    if(n <= 1) return n;    // 1 또는 0인 경우 n을 반환
    else {
        if(m[n] == -1){ // 메모이제이션이 기록되지 않은 경우
            int ans = INT_MAX;
            for(int i = pow(n, 0.5); i >= 1; i--)   // 선택 가능한 숫자 선택
                ans = min(ans, 1 + recur(n - pow(i, 2)));
            m[n] = ans;	// 메모이제이션 배열에 기록
            return ans; 
        }else return m[n];  // 기록된 경우 저장된 값을 반환
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    fill(m, m + 50001, -1);	// 메모이제이션 배열 초기화
    cout << recur(n);
}