[Swift][DP] 백준 1699번 (제곱수의 합)

요구능력 : DP에 대한 이해

 

코드설명 : 

우리는 여기서 최소개수를 구해야한다.

모든 경우의수를 비교해서 최소개수를 구하면 된다. 

 

11은 최소 3개항의 제곱수로 표현 가능하다고 한다.

1부터 8까지만 찾아보자.

1

1의제곱

 

2

1의제곱 + 1의제곱

 

3

1의제곱 + 1의제곱 + 1의제곱

 

4

1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱

2) 2의제곱

 

5

1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱

2) 1의제곱 + 2의제곱

 

6

1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱

2) 1의제곱 + 1의제곱 + 2의제곱

 

7

1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱

2) 1의제곱 + 1의제곱 + 1의제곱 + 2의제곱

 

8

1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱

2) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 2의제곱

3) 2의제곱 + 2의제곱

 

이렇게 나온다.

 

모든 경우의수를 비교해야한다. 비교해서 최대값을 구하는거라면, 그냥 처음에 0넣어놓고 max()함수를 사용하면된다.

하지만, 우리가 구할것은 최소값이다. 그렇다면 처음 dp[i]에는 dp[i]가 가질 수 있는 최대값이 들어있어야 한다.

dp[i]의 최대값은 전부다 1의제곱으로 더하면 최대값이 나온다.

 

위에 구해놓은 경우의수들을 보고 dp 식을 세워보자.

dp[1] = 1

dp[2] = 2

dp[3] = 3

여기까진 평범하다.

 

dp[4]

1) 4

2) 1 

여기서 우리가 구하고자하는 수는 최소값이기 때문에 2번이다.

계속 구해보자

 

dp[5]

1) 5

2) 2

 

dp[6]

1) 6

2) 3

 

dp[7]

1) 7

2) 4

 

dp[8]

1) 8

2) 5

3) 2

 

이것과 위의 경우의수를 보면 식이 나온다.

우선, 식을 적어보면 아래와 같다.

dp[i] = min(dp[i], dp[i - j * j ] + 1)

 

dp[i]와 비교해서 최소값을 구하는 이유는 dp[i]는 j가 도는도중의 가장 작은수가 들어가야하기 때문이다.

 

하나만 예로들어 식을 설명하면,

dp[8]이 있다.

(참고 : +1을 해주는 이유는 제곱수만큼 빼줘서 제곱수가 들어갈 1개의항을 더해준거다.)

j = 1일 때,

dp[8] = min(dp[8], dp[8 - 1] + 1)

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

여기서 1의제곱을 빼주고 1의제곱의 항을 +1해준거다.

 

j = 2

dp[8] = min(dp[8], dp[8 - 4] + 1)

1 + 1 + 1 + 1 + 2의제곱(j * j)

여기서 2의제곱을 빼주고 2의제곱의항을 +1 해준거다.

 

dp[7]과 dp[4]의 최소값은 dp[8]을 돌기전에 이미 구해져있다.

이렇게 쭉 비교하고나면 가장 적은 항을 가진 제곱수의 합이 나오게된다.

 

핵심은 가장 큰 제곱수를 빼주면 항이 작아진다는 것이다.

 

후기 : 쉽게 접근했다가는 풀지못하는 문제,,

이렇게 문제에 제곱수로하면 3개, 4개도 가능한데 여기서 최소를 찾아라.

이런거 나오면 그냥 쭉다 나열하고 찾아보는것도 하나의 방법인거같다.

수학 + DP의 합성인거같다.

let n = Int(String(readLine()!))!

var dp: [Int] = Array(repeating: 0,count: 100001)

for i in stride(from: 1,through: n,by: 1){
        dp[i] = i //1의 제곱으로만 이루어진 경우(최대값)
        for j in stride(from: 1, through: i, by: 1) {
            if j * j > i {
                break
            }
            dp[i] = min(dp[i], dp[i - j * j] + 1)
    }
}
print(dp[n])