백준 17626 파이선 | Four squares

코드

import sys

n = int(sys.stdin.readline())
ans = 0

lst = []

# 제곱수들 모음
for i in range(1,224):
    lst.append(i**2)
l = len(lst)

# 답이 3인 경우
for i in range(l):
    for j in range(l):
        for k in range(l):
            if lst[i] + lst[j] + lst[k] == n:
                ans = 3

# 답이 2인 경우
for i in range(l):
    for j in range(l):
        if lst[i] + lst[j] == n:
            ans = 2                

# 답이 1인 경우
for i in range(l):
    if lst[i] == n:
        ans = 1            

# ans가 1, 2, 3이 아니면 ans는 무조건 4
if ans == 0:
    ans = 4

print(ans)

설명

223의 제곱이 49729여서 lst에는 1 부터 223 까지의 제곱수를 저장해 놓는다.

다음으로 답이 3, 2, 1인 경우를 나누어 모든 경우의 수를 다 돌며 답을 찾는다.

최소인 답을 구해야 함으로 순서는 답이 3, 2, 1인 경우로 찾는다.

답은 1, 2, 3, 4 중에 하나니까 마지막 조건문에서 답이 1, 2, 3이 아닌 경우 4로 설정해준다.

 

224 * 224 * 224 = 11,089,567 으로 반복문을 세 번 돌아도 시간을 초과할 정도는 아니다.

 

메모리: 124368KB

시간: 184ms

문제

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

17626번: Four Squares