[Python] 백준 #17626- Four Squares

문제

---

17626번: Four Squares

코드

---

My answer

import sys
input = sys.stdin.readline

n=int(input())
dp=[0]*(n+1)
array=[]

for i in range(int(n**0.5)+1):
    dp[i*i]=1
    
for i in range(1,n+1):
    for j in range(1,int(i**0.5)+1):
        if(dp[i]==0):dp[i]=dp[j*j]+dp[i-j*j]
        else:
            dp[i]=min(dp[i],dp[j*j]+dp[i-j*j])
    
print(dp[n])

Another answer

import math

n = int(input())
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1

for i in range(2, n + 1):
    if i == int(math.sqrt(i)) ** 2:
        dp[i] = 1
    else:
        dp[i] = i

for i in range(2, n + 1):
    for j in range(1, int(math.sqrt(i)) + 1):
        dp[i] = min(dp[i], dp[j * j] + dp[i - j * j])
print(dp[n])

L1=[x*x for x in range(1,224)]
L2=[i+j for i in L1 for j in L1 if i+j<50001];S2=set(L2)
L3=[i+j for i in L1 for j in S2 if i+j<50001];S3=set(L3)
N=int(input())
if N in L1:print(1)
elif N in S2:print(2)
elif N in S3:print(3)
else:print(4)

n = int(input())
L = set([i*i for i in range(1, 224)])
if n in L:
    print(1)
    exit()
for i in range(1, int(n**0.5)+1):
    if (n-i*i) in L:
        print(2)
        exit()
for i in range(1, int(n**(0.5)+1)):
    for j in range(1, int(n**0.5)+1):
        if (n-i*i-j*j) in L:
            print(3)
            exit()
print(4)

풀이

---

우선 이번 문제는 dp로 풀 경우 pypy3로 제출해야만 통과할 수 있는 것 같다. dp로 푼 분들 중 python3으로 해결한 사람을 찾지 못했다. 정 python3로 통과하고싶으면 브루트포스로 해결해야 했다.

우선 내 방법과 another answer 1이랑 똑같은 방법인데, 우선 제곱수의 경우 모두 1로 바꿔준다.(이것도 난 무식하게 구했는데, math.sqrt를 이용해서도 할 수 있는 것 같다.) 그리고 이제 dp[1]부터 반복문을 순회하면서 현재 i보다 작은 제곱수들로 만들 수 있는 모든 조합을 생각해봐야한다. 예를 들어 dp[6]=min(dp[1]+dp[5],dp[4]+dp[2]) 이런식으로. 왜냐하면 항상 가장 가까운 제곱수로 만든 것이 최소가 아니기 때문이다. 예를 들어 예시에 있는 11339의 경우는 105^2 + 15^2 + 8^2 + 5^2가 정답인데, 11339에 가장 가까운 제곱수는 106**2이기 때문이다. 따라서 모든 i보다 작은 제곱수들로 만들 수 있는 경우를 확인해봐야 했다. 

anothwer answer4가 브루트포스로 푼 가장 직관적인 방법인 것 같은데, 모든 수는 문제에서도 알 수 있듯이 최대 4개의 제곱수의 합으로 만들 수 있기 때문에, 1개의 제곱수로 만드는 경우, 2개의 제곱수로 만드는 경우, 3개의 제곱수로 만드는 경우를 확인하고 그 외는 모두 답이 4인 것을 활용한 브루트포스 해결 방법이었다.