백준 16991 [백준] 1699번 제곱수의 합 - JAVA https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 다이내믹 프로그래밍을 이용한 문제다. 1, 4, 9, 16.. 과 같은 제곱수를 활용하여 주어진 수 N을 최소한의 개수로 구성하는 것이 답이다. 최적의 값을 idx에 기억해두는 바텀업 방식으로 이중 for문을 사용했다. 해당 문제에서 최적의 값은 최소한의 연산 횟수다. DP 테이블 초기화 먼저 dp 테이블을 idx는 숫자, value는 최소 연산 횟수로 사용.. 2022. 6. 8. 이전 1 다음