BOJ 1699 - 제곱수의 합

Joonas' Note

BOJ 1699 - 제곱수의 합 본문

알고리즘/문제 풀이

BOJ 1699 - 제곱수의 합

2019. 11. 6. 20:46 joonas 읽는데 1분
  • 문제
  • 코드

링크: https://www.acmicpc.net/problem/1699

문제

주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다.

문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다.

백준 온라인 저지에 문제로도 등장했다.

BOJ 3933 - 라그랑주의 네 제곱수 정리

요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다.

xa+yb+zc+wd=N 에서 a, b, c, d 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 a, b, c를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다.

즉, 3중첩 반복문으로 해결 가능하다.

코드


'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 1308 - D-Day  (0) 2019.11.10
BOJ 17520 - Balanced String  (0) 2019.11.07
BOJ 17521 - Byte Coin  (0) 2019.11.06
BOJ 5612 - 터널의 입구와 출구  (0) 2019.11.06
BOJ 13325 - 이진 트리  (0) 2019.09.16
Comments