Joonas' Note

Joonas' Note

BOJ 1699 - 제곱수의 합 본문

알고리즘/문제 풀이

BOJ 1699 - 제곱수의 합

2019. 11. 6. 20:46 joonas

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

    문제

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

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

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

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

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

    \(x^a + y^b + z^c + w^d = 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