제곱수의 합1 [백준] BOJ1699 제곱수의 합 DP 문제https://www.acmicpc.net/problem/1699 특정수를 제곱수의 합으로 나타낼 때, 그 항의 최소 개수를 구하는 문제이다.즉 12 를 제곱수(1, 4, 9, 16, ...)의 합으로 구하는 방법은 아래와 같이 여러개가 존재한다.1) 9 + 1 + 1 + 1 (4항)2) 4 + 4 + 4 (3항)3) 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 (9항) 즉, 12 를 표현하는 항의 최소 개수는 3항 임을 알 수 있다.여기서 조심해야 할 점은, 사용할 수 있는 제곱근 중 가장 큰 수 ( = 9) 를 사용하는 1번 방법이 항상 좋은 것은 아니다.그렇기 때문에, dp를 이용하여 풀어나간다. dp 배열은 i 값을 제곱근의 합으로 나타냈을 때 가장 최소값을 가진다. **.. 2018. 11. 4. 이전 1 다음