[BaekJoon] 백준 17626번 Four Squares

[BaekJoon] 백준 17626번 Four Squares

 

문제: https://www.acmicpc.net/problem/17626

 

내코드

 

문제 내용은 간결했지만 어떤식으로 풀어야 할지 생각이 필요했던 문제다. 더군다가 시간도 0.5초로 짧은 편이라서 무작정 구현하기에는 무리였다.

 

문제에서 가장 중요한 조건은 결국 어떤 수든 답은 1, 2, 3, 4 중에 하나라는 의미이다. 즉, 주어진 수가 정수의 제곱수면 1, 어떤 정수 i에 대해 n - i^2의 제곱근이 정수면 2, 어떤 정수 i, j에 대해 n - i^2 - j^2의 제곱근이 정수면 3, 그외의 경우는 모두 4라는 의미이다. 

 

# BaekJoon17626.py

def solution(n):
    # n이 제곱근이 정수라면 답은 1
    if int(n**0.5) == n**0.5:
        return 1
    # 1 ~ (n의 제곱근의 올림값)을 i라고 하고 (n - i^2)의 제곱근이 정수라면 답은 2
    for i in range(1, int(n**0.5) + 1):
        if int((n - i**2)**0.5) == (n - i**2)**0.5:
            return 2
    # (n - i^2 - j^2)의 제곱근이 정수라면 답은 3
    for i in range(1, int(n**0.5) + 1):
        for j in range(1, int((n - i**2)**0.5) + 1):
            if int((n - i**2 - j**2)**0.5) == (n - i**2 - j**2)**0.5:
                return 3
    # 1, 2, 3도 아닌경우 답은 4
    return 4


n = int(input())
print(solution(n))

 

참고

https://moz1e.tistory.com/268