[실버 III] 17626번. Four Squares

 문제 

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

17626번: Four Squares

 사용 언어 

Python3

 풀이 과정 

DP를 이용해 풀었는데 Python3로는 시간 초과로 실패했다.

from sys import stdin
input = stdin.readline

n = int(input())
# dp[i] = 숫자 i가 가지는 제곱수 합 최소개수
dp = [float("inf")] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
    for j in range(1, i+1):
        double = j * j
        if double > i:
            break
        dp[i] = min(dp[i], dp[i - double] + 1)

print(dp[n])

몇 군데를 고쳐보았지만 여전히 Python3로는 실패하고 Pypy3로는 맞았습니다!!

다른 문제에 대한 코드 리뷰로 최댓값, 최솟값을 갈아끼울 때 무조건 max(), min() 함수를 사용하는 것보다 크거나 작은 상황을 if문으로 확인하고 맞을 때만 갈아끼우는 게 더 빠르다는 조언이 있었다.

따라서 이번에도 그렇게 변경해보았더니 아마 저 로직이 많이 돌기 때문에 24ms나 빨라진 걸 볼 수 있었다!! (140ms)

 

그러고 나서 break하는 조건문을 빼고 j의 범위를 제곱근까지로 변경해보았는데 그건... 오히려 184ms로 늘어났다..?

뭔가 범위 계산을 잘못한 거겠지?_?

 

 제출 답안 

# Pypy3 140ms 버전
from sys import stdin
input = stdin.readline

n = int(input())
# dp[i] = 숫자 i가 가지는 제곱수 합 최소개수
dp = [float("inf")] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
    for j in range(1, i + 1):
        double = j * j
        if double > i:
            break
        if dp[i] > dp[i-double] + 1:
            dp[i] = dp[i-double] + 1
print(dp[n])

 

 다른 사람 코드 

1. 어쨌든 Python3로도 다른 사람들은 잘만 푸는 문제이기 때문에... 백준 맞힌 사람에서 코드를 좀 찾아봤다.

n = int(input())
u = int(n**(1/2))
m = list([k**2 for k in range(1, 224)])
for i in m:
    if i == n:
        print(1)
        exit()
for i in m:
    if n-i in m:
        print(2)
        exit()
while n%4==0:
    n=n//4
if n%8==7:
    print(4)
    exit()
else:print(3)

➡ 코드 분석(?) 결과는 다음과 같다.

 

1. 입력값 n의 제곱근을 구하고 최대 50000까지만 고려하기 때문에 루트 50000 = 223.xx임에 따라 224까지 제곱수를 모두 구해 리스트로 만들어둔다.

2. 그리고 제곱수를 분류하는데, n과 같으면 바로 1을 출력, n과 다른 제곱수의 차이가 또 제곱수이면 2를 출력한다.

3. 위 두 가지 경우에 해당하지 않으면 n이 4의 배수가 될 때까지 n을 4로 나누고, 만약 그 수를 8로 나눴을 때 나머지가 7이면 4를 출력, 아니면 3을 출력한다.

 

??? 마지막 3번이 아예 이해가 안가는데 아마도.. 수학적인 이론을 이용한 것 같다.

 

2. 조금은 더 이해가 쉬운 코드였다. 내가 제출해서 돌려보니 76ms가 나왔다.

import sys
def check(n) :
    if (n**0.5).is_integer() : return 1
    for i in range(1, int(n**0.5)+1) :
        if (int(n-i*i)**0.5).is_integer() : return 2
    for i in range(1, int(n**0.5)+1) :
        for j in range(1, int((n-i*i)**0.5)+1) :
            if ((n-i*i-j*j)**0.5).is_integer() : return 3
    return 4

n = int(sys.stdin.readline())
print(check(n))

➡ 이렇게 하면 결국 완전 탐색 방법인데, DP보다 더 빠르다는게... 왜인지 모르겠다😂 아마도 DP에서 제곱수를 계산해서 찾는 과정의 연산이 더 오래 걸리나보다.

 

출처 : https://kau-algorithm.tistory.com/m/291