Four Squares1 [C/C++] 17626: Four Squares 일단 bruteforce하게 구현한 코드이다.(굳이 말하면 dp를 조금 이용하여 계산 수를 줄임) 먼저 제곱수는 최소 개수의 제곱수의 합이 1이므로 먼저 dp배열에 저장해준다. 최소개수의 제곱수의 합이 2인 수들은 최소 개수의 제곱수의 합이 1인 수 2개의 합이므로 MakeContinue 함수를 이용해 구하고 최소개수의 제곱수의 합이 3인 수들은 최소 개수의 제곱수의 합이 1인 수와 최소 개수의 제곱수의 합이 2인 수들의 합이므로 이를 이용해서 구하면 된다. 그리고 마지막으로 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로 dp[i]==0인 경우에 최소개수의 제곱수의 합이 4인것을 알 수 있다. #include #include int dp[100001]; //int tmp=cpy_o.. 2023. 8. 22. 이전 1 다음