728x90 제곱수1 [Python] 백준 1699 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제해결 dp를 이용해야겠다라는 생각이 든다! - y를 제곱수의 합으로 표현할 때 최소개수를 dp[y]라고 하고 x를 y보다 작은 제곱수라고 가정하면 dp[y] = min(dp[y], dp[y-x] + 1) 만약 어떤 수 y가 제곱수이면 dp[y] = 1 인 것이 명백하므로 먼저 제곱수는 dp[y] = 1을 고정시키자. for 문을 쓰면 될 것 같은데? co.. 2022. 12. 25. 이전 1 다음 728x90
