백준 17626번 four squares

 

시간제한이 좀 빡빡하다.

 

완전탐색하면 시간초과일 가능성이 농후하다.

dp로 푸는 문제인듯하다.

 

가장 큰 제곱수를 구하고 그 뒤 나머지는 저장된 값을 불러오게 하면 될듯하다.

import sys

n=int(sys.stdin.readline().rstrip())
v=[0]*(n+1)

v[1]=1
v[2]=1
v[3]=1

for i in range(4,n+1):
    v[i]=v[i-pow(int(i**(0.5)),2)]+1

print(v[n])

생각을 잘못했다. 일단 초기값을 안넣어도 될거같고 나올 수 있는 경우의 수중 최소값을 골라줘야한다.

 

예를 들어 23은 9+9+5로 해주는게 가장 갚이 낮다. 16+7로하면 5가 나온다.

 

import sys

n=int(sys.stdin.readline().rstrip())
v=[0]*(n+1)

for i in range(1,n+1):
    result=0
    for j in range(1,int(i**(0.5))+1):
        if result==0:
            result=v[i-pow(j,2)]+1
            continue
        result=min(result,v[i-pow(j,2)]+1)
    v[i]=result

print(v[n])

수정했다.

당연한 말이지만 많이 느려졌다.

o(n√n)인데 안되네

pypy는 된다.

 

근데 o(n)으로 하는방법이 있을듯하다.

import sys

n=int(sys.stdin.readline().rstrip())
v=[0]*(n+1)

for i in range(1,n+1):
    if i==1:
        v[1]=1
        continue
    elif i==2:
        v[2]=2
        continue
    elif i==3:
        v[3]=3
        continue
    result=0
    
    v[i]=min(v[i-pow(int(i**(0.5)),2)],v[i-pow(int(i**(0.5))-1,2)])+1

print(v[n])

이렇게도 해봤는데

모르겠다.

수학적으로 푸는게 아니라면 n√n이 최선이 맞는거같다.

gpt님도 그렇다고 한다.

억울하면 c++써야지