완전탐색(유형정리) - 백준 17626

17626번: Four Squares (acmicpc.net)

17626번: Four Squares

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

예제 입력 1 복사

25

예제 출력 1 복사

1

예제 입력 2 복사

26

예제 출력 2 복사

2

예제 입력 3 복사

11339

예제 출력 3 복사

3

 

예제 입력 4 복사

34567

예제 출력 4 복사

4

 

 

문제는 위와 같다. 앞 문제들에 비해 문제 자체를 이해하는 것은 상당히 쉬운일이었다. 결국 제곱수로 어떤 수든 나타낼 수 있다는 말로 몇개로 나열이 되냐는 것을 찾는 문제였다. 이 문제의 핵심은 결국 무슨 수이든지 4개의 제곱수로 표현이 가능하다는 것이다. 그 점을 인식하고 브루트포스 형식에 맞게 계속 제곱수를 찾도록 n에다 제곱수를 빼는 형식으로 return을 시켜주었다.

 

import math

def Four_Squares(n):
    if int(math.sqrt(n)) == math.sqrt(n):
        return 1

    for i in range(1, int(math.sqrt(n)) + 1):
        if int(math.sqrt(n - pow(i,2))) == math.sqrt(n - pow(i,2)):
            return 2

    for i in range(1, int(math.sqrt(n)) + 1):
        for j in range(1, int(math.sqrt(n - pow(i,2))) + 1):
            if int(math.sqrt(n - pow(i,2) - pow(j,2))) == math.sqrt(n - pow(i,2) - pow(j,2)):
                return 3

    return 4
n = int(input())
print(Four_Squares(n))

 

코드는 위와 같다. 소수 완전탐색 시 결국 n자체 보다는 루트를 씌운 math.sqrt(n)을 통해 시간복잡도를 줄이는 방식을 택했었던 것을 떠올리고 위와 같이 int형으로 나타내 준 것과 아닌 상태를 비교하여 같을 때를 살펴본다.

 

1. 제곱수이면 return 1

2. n - 제곱수이면 return 2

3. n - 제곱수 - 제곱수이면 return 3

4. 아닌 모든 경우에서 return 4

 

이 형식을 그대로 지켜서 입력받은 n을 호출시켜주면 끝!!!