원래 문제: https://gist.github.com/MetaFibonacci/cf55fbc53dd359ea89c503659e791fec
1. 풀이과정
다항식을 행렬로 표현한 다음에 계산->정렬->형식대로 출력하는 식으로 풂
1) 다항식->행렬
ex) 5f^2f'^5f'''^2+2f'^3
-> 계수 |5 2|
지수 f |2 0|
지수 f' |5 3|
지수 f'' |0 0|
지수 f'''|1 0|
2) 계산
(1) 미분 계산
singleColDiff=(array::Vector{Int64})->begin
temp=Vector{Int64}[]
for i in 2:length(array)
if array[i]==0
else
newArr=zeros(Int64, length(array)+1)
newArr[1:end-1]=array
newArr[1]*=newArr[i]
newArr[i]-=1
newArr[i+1]+=1
push!(temp, newArr)
end
end
return hcat(temp...)
end
matrixDiff=(matrix::Matrix{Int64})->begin
temp=Matrix{Int64}[];
for i in 1:(size(matrix)[2])
push!(temp, singleColDiff(matrix[:,i]))
end
return hcat(temp...)
end
addLikeTerms=(matrix::Matrix{Int64})->begin
temp=Vector{Int64}[];
for i in 1:(size(matrix)[2])
vec=matrix[:,i]
if vec[1]==0
else
vecToAppend=deepcopy(vec)
for j in (i+1):(size(matrix)[2])
iterMat=matrix[:, j]
if vecToAppend[2:end]==iterMat[2:end]
vecToAppend[1]+=iterMat[1]
matrix[1, j]=0
end
end
push!(temp, vecToAppend)
end
end
return hcat(temp...)
end
(2) 점화식 계산
recurMat=(n::Int64)->begin
if n==1
return hcat([1, 0])
elseif n==2
return hcat([-1, 0, 1])
else
front=matrixDiff(recurMat(n-1))|>
addLikeTerms
front[2,:].+=2^(n-2)
backTemp=recurMat(n-1)
a,b=size(backTemp)
back=zeros(Int64, a+1, b)
back[1:end-1,:]=backTemp
back[1,:].*=-(2^(n-2))
back[2,:].+=(2^(n-2)-1)
back[3,:].+=1
temp=hcat(front, back)|>
addLikeTerms
return temp
end
end
3) 정렬
sortMat=(matrix::Matrix{Int64})->begin
length=size(matrix)[1]
for i in 2:length
matrix=sortslices(matrix, dims=2, by=x->x[i])
end
return matrix
end
4) 출력
formatPrint=(matrix::Matrix{Int64})->begin
temp=String[]
for j in 1:(size(matrix)[2])
newStr=""
for i in 1:(size(matrix)[1])
if i==1
if matrix[i,j]==1
elseif matrix[i,j]==-1
newStr*="-"
else
newStr*="$(matrix[i,j])"
end
elseif matrix[i,j]==0
elseif i>1&&i<6
if matrix[i,j]==1
newStr*="f" * "'"^(i-2)
else
newStr*="f" * "'"^(i-2) * "^{$(matrix[i,j])}"
end
else
if matrix[i,j]==1
newStr*="f_{$(i-2)}"
else
newStr*="f_{$(i-2)}^{$(matrix[i,j])}"
end
end
end
push!(temp, newStr)
end
returnStr=join(temp, "+")
returnStr=replace(returnStr, "+-"=>"-")
return returnStr
end
5) 입력 받기
houseHolder=(n::Int64)->begin
nthMat=recurMat(n)
prevMat=recurMat(n-1)
minN=min(nthMat[2,:]...)
minP=min(prevMat[2,:]...)
addVal=2^(n-2)
if minN<minP+addVal
nthMat[2,:].-=minN
prevMat[2,:].+=addVal-minN
else
nthMat[2,:].-=minP+addVal
prevMat[2,:].-=minP
end
prevMat|>
sortMat|>
formatPrint|>
println
nthMat|>
sortMat|>
formatPrint|>
println
end
hhLoop=()->begin
while true
a=readline()
intA=parse(Int64, a)
houseHolder(intA+1)
end
end
hhLoop()
2. 결과
적어도 n이 1~4일 때까지는 잘 들어맞는 것 확인함
속도야 julia가 늘 그렇듯이 첫 실행은 컴파일하느라 좀 걸리고 그 다음부터는 괜찮음
n=4, 8, 15에 대해서 벤치마킹 했을때 대충 요럼. 실행은 라즈베리파이4(BCM2835)에서 함.
n=25도 해보고 싶었는데 아무리 기다려도 안 됨
문제 조건 다는 못지켰는데 일단 기본적인 것들은 웬만큼 한듯
댓글 1