https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 1. Logic dp배열에는 해당 숫자를 만들수 있는 최소 갯수를 저장한다. 숫자를 중복해서 골라도 되고 해당 숫자를 고를수도, 안고를 수도 있으니 i*i를 구하는 for문 안에서 숫자를 선택하는 경우 선택하지 않는 경우를 반영해준다. 2. Code #include using namespace std; int n; int dp[50001]; int solve(i..
'17626 topdown' 태그의 글 목록