빠똥빠똥
1699번 제곱수의 합(DP) - ☆ 본문
#문제링크 : https://www.acmicpc.net/problem/1699
<전략>
1. n을 제곱수의 합으로 나타낼때, i가 포함된다고 하면, n = i^2 + ... 이렇게 나타낼 수 있다.
2. n - i^2을 제곱수의 합으로 나타낼때, j가 포함된다고 하면, n - i^2 = j^2 + ... 이렇게 나타낼 수 있다.
3. d[n] = min(d[n-i^2] + 1) 이다. +1은 i^2이 포함되기 때문.
'백준' 카테고리의 다른 글
| 9461번 파도반 수열(DP) (0) | 2020.06.24 |
|---|---|
| 2133번 타일채우기(DP) - ☆ (0) | 2020.06.24 |
| 1912번 연속합(DP) - ☆ (0) | 2020.06.23 |
| 11054번 가장 긴 바이토닉 부분 수열(DP) - ☆ (0) | 2020.06.22 |
| 11053번 가장 긴 증가하는 부분 수열(DP) - ☆ (0) | 2020.06.22 |
'백준' Related Articles
more
