16198번 에너지 모으기 백준 파이썬

문제:www.acmicpc.net/problem/16198

16198번: 에너지 모으기

 

import sys
input=sys.stdin.readline
N=int(input())
li=list(map(int,input().split()))
visited=[False]*N
visited[0]=True
visited[-1]=True
ans=list(li)
ret=0
 
def func(sum,x):
    global ret
    if all(visited):
        ret=max(ret,sum)
        return
    for i in range(1,N):
        if not visited[i]:
            visited[i]=True
            x[i]=-1
            left=0
            right=0
            for j in range(i-1,-1,-1):
                if x[j]!=-1:
                    left=x[j]
                    break
            for k in range(i+1,N):
                if x[k]!=-1:
                    right=x[k]
                    break
            tmp=left*right
            sum+=tmp
            func(sum,x)
            sum-=tmp
            x[i]=li[i]
            visited[i]=False
          
func(0,ans)
print(ret)

 

위 코드는 내가 작성한 코드이다. 

풀이 방법은 현재 방문 할 점은 -1로 바꾸고 현재 기준점으로 왼쪽에서 가까운 값 중 -1이 아닌것과 오른쪽에서 -1이 아닌 값을 찾은 다음에 곱해서 sum에 더한다음 재귀형식으로 돌리는 형식이다.

코드 실행하면서 느낀점은 시간복잡도에 대한 것이 좀 아쉽고 길이가 다른 코드들에 비해 길었다는 것이 아쉬웠다.

그래서 다른 분의 코드를 참고했다.

 

 

n=int(input())
L=list(map(int,input().split()))
def f(L):
    if len(L)==3: return L[0]*L[2]
    ret=0
    for i in range(1,len(L)-1):
        r=L[i-1]*L[i+1]+f(L[:i]+L[i+1:])
        ret=max(ret,r)
    return ret
print(f(L))

위 코드를 설명하자면 base case는 길이가 3일때 0번째 값과 2번째 값을 곱한것을 return한다.

재귀에 관한 것은 7번째 줄에 해당한다. 기준으로부터의 양변의 값을 곱하고 기준점을 제외한 리스트의 값을 더한 것을 구하고 현재 ret과 구한 값의 대소관계를 구하고 return하는 형식이다.