백준 C# - 1699 +) 풀이

문제

정수 n이 주어졌을때 n을 제곱수들의 합으로 표현하는 방법 중에서 항의 개수가 최소인 경우의 수를 구해야한다.

예시
12 = 4 + 4 + 4
13 = 9 + 4

 

점화식 생각

01 dp[] 배열에 어떤 값을 넣을까?

i를 만들기 위한 최소 제곱수들의 합으로 표현할 때 필요한 항의 수

02 i를 만들기 위해 바로 전 단계는 뭘까?

이미 dp[i-j*j]값을 알고있음 그래서 이번 값에서 + 1

그래서 나온 점화식

dp[i] = min(dp[i-j²]+1) (단 j²<=i)

예시) n = 5

- dp[1]
가능한 j: 1 (1²)
dp[1] = min(dp[1], dp[1 - 1] + 1) = min(∞, dp[0] + 1) = 1
dp[1] = 1

- dp[2]
가능한 j: 1 (1²)
j=1: dp[2] = min(dp[2], dp[1] + 1) = 1 + 1 = 2
dp[2] = 2

- dp[3]
가능한 j: 1 (1²)
j=1: dp[3] = dp[2] + 1 = 2 + 1 = 3
dp[3] = 3

- dp[4]
가능한 j: 1 (1²)
가능한 j: 2 (2²)
j=1: dp[3] + 1 = 4
j=2: dp[0] + 1 = 0 + 1 = 1 
dp[4] = 1

- dp[5]
가능한 j: 1 (1²)
가능한 j: 2 (2²)
j=1: dp[4] + 1 = 1 + 1 = 2
j=2: dp[1] + 1 = 1 + 1 = 2
dp[5] = 2

---

코드 전문

int dp[] = new int[n+1];
dp[0] = 0;

for (int i = 1; i <= n; i++)
{
    dp[i] = i; // 최악의 경우 (1^2을 i번 쓰는 경우)
    for (int j = 1; j * j <= i; j++)
    {
        dp[i] = Math.Min(dp[i], dp[i - j * j] + 1);
    }
}