[C++/백준] 1699번: 제곱수의 합

문제 바로가기

문제 해결 아이디어

• 점화식 도출 과정
  1. DP[N] = A 를 N이 되기 위해 필요한 최소항의 개수 A 로 정의
  2. DP[0] = 0이 되기 위해 필요한 최소항의 개수는 0개
  3. DP[1] = 1이 되기 위해 필요한 최소항은 $1^2$ 이므로 1개
  4. DP[2] = 2가 되기 위해 필요한 최소항은 $1^2$+ $1^2$ 이므로 2개
  5. DP[3] = 3이 되기 위해 필요한 최소항은 $1^2$+ $1^2$+ $1^2$ 이므로 3개
  6. DP[4] = 4가 되기 위해 필요한 항은 $2^2$, $1^2+ 1^2+ 1^2+ 1^2$ 두가지 경우가 존재하는데, 이중 최소항은 $2^2$ 이므로 1개
  
  
• 규칙 살펴보기
  1. DP[2]는 DP[1] + 1이고, DP[3]은 DP[2] + 1이다.
  2. DP[4]와 같이 N이 제곱수인 경우, DP[3] + 1과 $2^2$을 비교하면, $2^2$이 최소항 이므로 1이다.
  3. DP[8]의 경우, N이 제곱수는 아니지만 DP[7] + 1과 $2^2+ 2^2$를 비교하면, 최소항이 $2^2+ 2^2$이므로 2이다.
  이때, $2^2+ 2^2$에서 $2^2$은 DP[4]의 최소항이고, DP[4]를 이용하여 DP[8] = DP[4] + 1로 나타낼 수 있다. 따라서, DP[8] = min(DP[7] + 1, DP[4] + 1)
  
  
• 점화식 도출
  따라서, DP[N]의 최소항의 개수는 DP[N - 1] 부터 DP[0] 까지 반복하며 +1 한 값들 중 최솟값이 된다.
  DP[N] = min(DP[N - i^j]) (i = 1 ~ N, j = 1 ~ j * j <= i)

코드