BAEKJOON #17626 Four Squares (DP, Brute force) - python

nathan29849·2021년 8월 25일
0

알고리즘문제

목록 보기
51/92

Four Squares

출처 : 백준 #17626

시간 제한메모리 제한
0.5초512MB

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

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


입력

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


출력

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


입출력 예시

예제 입력 1

25

예제 출력 1

1


예제 입력 2

26

예제 출력 2

2


예제 입력 3

11339

예제 출력 3

3


예제 입력 4

34567

예제 출력 4

4


풀이

생각 및 풀이 설명

  • DP 문제로 접근하였다.

  • base case로 n보다 같거나 작은 수들 중 제곱으로 표현할 수 있는 수는 dp[i] = 1로 정했다.

  • for 문을 돌면서 제곱으로 나타낼 수 있는 수가 아니라면(=dp[i] != 1), 현재의 인덱스에서 제곱으로 나타낼 수 있는 수를 빼준 값을 인덱스로 하여, 인덱스에 해당하는 수들을 비교한 후 가장 작은 값에 1을 더하여 준다.

    • 1을 더하는 이유 : 예를들어 8을 나타내려고 할 때 8보다 작은, 제곱으로 나타낼 수 있는 수는 1과 4가 있다.
    • 그럼 8-1, 8-4 즉, 7과 4에 해당하는 값을 찾아야 한다.
    • 이때 dp[7] = 4, dp[4] = 1이다.
    • 4로부터 4만큼 더해주면 되므로, 1을 추가해주는 것이다.
  • 이 문제는 내가 짠 코드로는 python3 기준 시간초과가 발생했다.

  • 그러나 pypy로 했더니 통과했다. (가끔은 이렇게 pypy로 통과하는 경우가 있으니 알아두자.)

  • python3로 풀 수 있는 코드는 1, 2, 3, 4로 경우를 나누어 푼 코드이다.(DP 이용 X)

    • 4이하의 자연수로 표현할 수 있기 때문이다.

python code(pypy3에서 정답, python3 시간초과)

# 백준 17626번 Four Squares
from sys import stdin
input = stdin.readline

n = int(input())
dp = [0] * (n+1)
i = 1
squareArr = []
while i**2 <= n:
    dp[i**2] = 1
    squareArr.append(i**2)
    i += 1

for j in range(1, n+1):
    if dp[j] != 1:
        temp = 4
        for x in squareArr:
            if x <= j:
                if dp[j-x] <= 3:
                    if dp[j-x]+1 < temp:
                        temp = dp[j-x] + 1
            else:
                break
        dp[j] = temp

print(dp[n])

python code(python3 정답)

import sys
input = sys.stdin.readline
n=int(input())

def is_square(n):
    if n==int(n**0.5)**2:
        return True
    else:
        return False
def is_two(n):
    for i in range(int(n**0.5) ,0,-1):
        if i**2<n/2:
            return False
        if is_square(n-i**2):
            return True
    return False
def is_three(n):
    for i in range(int(n**0.5),0,-1):
        # print('i2',i)
        if is_two(n-i**2):
            return True
        if i**2<n/2:
            return False
    return False
if is_square(n): print(1)
elif is_two(n) : print(2)
elif is_three(n) : print(3)
else : print(4)
profile
"나는 날마다 모든 면에서 점점 더 나아지고 있다"

0개의 댓글