1699
BOJ 1699 제곱수의 합
boj 1699 제곱수의 합 수가 주어지면 그 수를 제곱수들의 합으로 표현할 때, 최소의 항 갯수를 구하는 문제이다. 모든 수는 1의 합으로 표현할 수 있기에 최대의 항 갯수는 입력된 수의 크기와 동일하다. 그러므로, 테이블 D[i]를 i를 제곱수의 합으로 표현할 때의 최소의 항 갯수라고 정의하면, D[i] = i 라고 초기 값을 지정해줄 수 있다. 최소의 항 갯수를 구하는 방법은 간단하다. i에서 i를 넘지 않는 제곱수를 빼면서 최소 항의 갯수를 변경해주는 것이다. 이를 점화식으로 나타내보자. D[i] = min(D[i], D[i - 제곱수]+1) 이때, +1을 해주는 이유는 제곱수에 해당하는 항 갯수를 더해주는 것이다. #include #include using namespace std; int n;..