17626. Four Squares

백준 17626번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

17626번: Four Squares

풀이

아이디어

아무리 봐도 마땅한 풀이 방법이 생각나지 않아서 다른 분들의 풀이를 참고했다. 그래도 잘 모르겠어서 일단 DP 문제라는 힌트만 얻고 다시 정리해봤다.

일단 DP라고 했으니 1부터 차근차근 적어 보았다.

기본적으로 제곱수는 1개의 제곱수의 합으로 나타낼 수 있으므로 n이 제곱수일 경우에는 DP[n]은 기본적으로 1이다.

그 외의 경우에는 이전 숫자에 1²을 더해서 나타낼 수 있으므로 DP[n] = DP[n-1] + 1 이라는 식을 세울 수 있는데 n = 8인 경우와 같은 예외상황이 있었다.

n = 1부터 차근차근 DP 배열을 채워나가다 보면, 현재 n보다 앞에 채웠던 값들은 모두 최선의 결과(최소 개수)일 것이다.

따라서 n = a + b일 경우에 dp[n] = dp[a] + dp[b]가 성립할 수 있고, 이 값은 최선의 결과라고 할 수 있다.

그래서 기본값(DP[n-1] + 1)과 DP[(n보다 작은 제곱수)] + DP[(n - n보다 작은 그 제곱수)]를 비교해서 더 작은 값을 DP[n]에 할당해 주면 그것이 바로 최선의 값이 된다. (n보다 작은 제곱수인 이유는 제곱수일 경우의 DP[n]이 1이기 때문이다.)

예를 들어보면… n = 8일 경우에 DP[n]은

• DP[7] + DP[1] (기본값)
• DP[4] + DP[4]

이 두 개의 값을 비교해서 구할 수 있는 것이다.

이렇게 알게 된 점화식을 코드로 적어 보면 아래와 같이 된다.

for(int i = 2; i <= n; i++){
  // 제곱수일 경우에는 그냥 넘어간다.
	if (dp[i] == 1)
		continue;
  // 기본값 넣어주기
	dp[i] = dp[i - 1] + 1;
	for(int j = 0; j*j <= i; j++)
		dp[i] = min(dp[i], dp[j*j] + dp[i - j*j]);
}

코드

/*
2022-1-31
17626_Four Squares
https://www.acmicpc.net/problem/17626
*/

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

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

    int n;
    int dp[50001];

    memset(dp, 0, sizeof(dp));
    dp[0] = 0;
    cin >> n;
    for(int i = 1; i * i <= n; i++)
        dp[i * i] = 1;

    for(int i = 2; i <= n; i++){
        if (dp[i] == 1)
            continue;
		dp[i] = dp[i - 1] + 1;
        for(int j = 0; j*j <= i; j++)
            dp[i] = min(dp[i], dp[j*j] + dp[i - j*j]);
    }

    cout << dp[n];

    return (0);
}