[백준] 17626번: Four Squares [C++]
알고리즘 분류: 다이나믹 프로그래밍, 브루트포스 알고리즘 문제 링크: https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 【 풀이 】 DP 문제이다. 즉 규칙을 먼저 찾는 것이 중요한 문제. n의 제곱수들의 최소 개수를 저장한 배열을 dp라고 가정하면, dp[n]은 항상 최적의 해가 된다고 볼 수 있다. 그리고 dp[제곱수]는 항상 그 값이 1이다. dp[1] =1 dp[2] = dp[1] + dp[1] dp[3..
Problem Solving/Baekjoon
2023. 5. 28. 12:02
