/<> 백준 17626번 : Four Squares (C언어)

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

 

 

문제를 잘 읽어야 하는 게, 처음에 자연수 4개 이하로 합을 표현할 수 있다는 점을 보지 않고 혼자 "7개 8개 이상으로 숫자가 많으면 경우의 수가 너무 많은데 어떻게 표현하지?" 생각하며 끙끙댔습니다. 그러고 문제를 다시 보니 4개 이하로 표현한다는 부분을 읽었습니다...ㅎㅎㅎ 문제는 DP를 이용해 풀면 됩니다.

 

 

1. 인덱스에 해당하는 숫자가 몇 개로 표현이 가능한 지 개수를 저장하는 배열 dp[50001]을 생성합니다.

 

2. dp[0] = 0, dp[1] = 1 로 dp 배열을 초기화합니다. (0은 경우의 수가 없고, 1은 1*1 로 표현 가능)

 

3. 제곱수인 경우를 비교합니다. 즉 dp[i + j]의 값을 구할 때 j가 제곱수인 경우에 <dp[i] + 1> 이 4보다 작은지 판별합니다. <dp[i] + 1>인 이유는 1이 k*k (k * k = j) 포함되기 때문입니다.

 

 

<코드>

#include <stdio.h>

int min(int a, int b) {
        return a > b ? b : a;
}

int main() {
        int n;
        scanf("%d", &n);
        int dp[50001];
        dp[0] = 0;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
                int num = 4;
                int j = 1;
                while(j * j <= i) { // i가 제곱수인 경우
                        num = min(num, dp[i - j * j]);
                        j++;
                }
                dp[i] = num + 1;
        }

        printf("%d\n", dp[n]);
        return 0;
}