[C] 백준 | 17626번 코드 - Four Squares

>문제

www.acmicpc.net/problem/17626

17626번: Four Squares

> 핵심

DP

아니면

삼중반복문

>풀이과정

어려웠다.

어떻게 풀어야하나 도통 생각이 안나서 그냥 반복문을 돌려서 어거지로 풀었는데 나는 DP로 풀고싶었다.

근데 도저히 생각이 안나서 다른사람 아이디어를 보고나서야 DP 방식이 이해가 됐다.

 

dp 배열에는 제곱수를 표현하는 최소 개수가 들어간다.

dp[0] = 0, dp[1] = 1으로 초기화.

 

그리고 반복문을 돌면서 dp를 채운다.

일단 dp[i] = 4로 둔다. (최대 4니까)

 

그리고 j = 1부터 sqrt(i) 까지 순회하면서 (dp[i - (j*j)]) < dp[i] 인지 체크해서 더 작은 값을 dp[i]에 넣는다.

 

i - (j*j) 에서 (j*j)를 더해야 i 값이 되니까, i를 만들 수 있는 제곱수들의 합들을 모두 체크해볼 수 있는것...?!

 

dp[26] =>

dp[26 - 1*1] = dp[25] = 1

dp[26 - 2*2] = dp[22] = ?

dp[26 - 3*3] = dp[17] = ?

...

dp[26 - 5*5] = dp[1] = 1

 

따라서 최솟값은 1, 거기에 제곱수를 한번 더 더해야하므로 dp[26] = 1 + 1 = 2가 된다

j가 sqrt(i)까지 도는 이유는 i가 하나의 제곱수로 표현이 되는 경우 dp[0] = 0을 찍게되므로 하나의 수로 표현이 되도록 할 수 있기 때문 (0 + 1 = 1)

 

dp[0] = 0이므로 만약 해당 수가 제곱수라면 한번만에 원하는 값을 얻을 수 있는 것

어째 글로 쓰니까 더 어려운 것 같다

 

>깨달은점

해도해도 어렵다 어휴

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int dp[50001];

int f(int n)
{
    dp[0] = 0;
    dp[1] = 1;
    if (dp[n] != 0) return n;

    for (int i = 2; i <= n; i++)
    {
        dp[i] = 4;
        for (int j = 1; j <= sqrt(i); j++)
        {
            dp[i - (j * j)] < dp[i] ? (dp[i] = dp[i - (j * j)]) : (dp[i]);
        }
        dp[i] += 1;
    }

    return dp[n];
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", f(n));

    return 0;
}