[백준] 1699 제곱수의 합 (Dynamic programming)
2020. 3. 2. 20:28
https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는
www.acmicpc.net
동적 계획법 문제였습니다.
자연수를 1부터 n까지 나열하며 최소의 제곱수의 합을 표현해보면서 점화식을 구해봅니다.
점화식
1. n이 완전제곱수일 경우 제곱수의 수는 1개
2. 나머지는 (해당수 - k 번째 제곱수 항의 수) + (k 번째 제곱수 항의 수) (k=1,2,3....)해나가며 최소값을 정해주면 됩니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 9251 LCS (0) | 2020.03.11 |
|---|---|
| [백준] 9466 팀 프로젝트(DFS, Cycle) (0) | 2020.03.04 |
| [백준] 11057 오르막 수 (DP) (0) | 2020.02.27 |
| [백준] 15686 치킨 배달 (Brute force) (0) | 2020.02.23 |
| [백준] 17779 게리 맨더링 2 (2) | 2020.02.22 |