제곱수의 합1 [백준] 1699번 제곱수의 합 JAVA (자바) 풀이 문제 1699번 (DP) : 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다 예를 들어 11 = 3² + 1² + 1² (3개 항) 또는 11 = 2² + 2² + 1² + 1² + 1² (5개 항) 가능하다 11 제곱수 항의 최소 개수는 3이다 주어진 자연수 N 제곱수 항의 최소개수를 구하는 프로그램 [입력] : 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) [출력] : 제곱수 항의 최소 개수를 출력 [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법 DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 탑다운 (Top.. 2024. 7. 1. 이전 1 다음