1699

🧷 문제 https://www.acmicpc.net/problem/1699 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제이다. 🛠 풀이 이 문제는 Bottom-Up 방식의 DP로 해결할 수 있다. Step 1. 먼저 DP table을 길이 n의 1차원 리스트로 만들어준다. 모든 항은 최대 i의 길이를 가지므로 (1+1+1+...+1) 값은 i로 초기화해준다. d = [i for i in range(n+1)] Step 2. 주어진 숫자가 제곱수라면 제곱수 항의 최소 개수는 항상 1이므로, 1부터 i까지 제곱수들을 빼가면서 뺀 숫자 + 1과 기존의 최소 개수를 비교하여 답을 구해준다. if dp[i] > dp[i - j*j] + 1: dp[i] = dp[i - j*j] +..