p_도둑질_42897

생각

dfs로 모든경우의 수를 탐색하면 될것이라고 생각햇다.

첫코드

answer = 0
house_num =0
def solution(money):
    global answer
    global house_num
    house_num = len(money)
    max_v = -1
    visited = [0] * house_num
    dfs(visited,0,money,0)
    # 1- 2 3- 1 4
    return answer

def dfs(visited, nowi , money,sum):
    global answer
    global house_num 
    if(sum>answer):
        answer=sum
    if(nowi>house_num-1):
        return
    print(visited,nowi,sum)
    if(money[nowi]>0 and visited[nowi]==0):
        if not isNearbyVisited(visited,nowi):
            print("visit")
            visited[nowi]=1
            # 방문을 한경우
            dfs(visited,nowi+2,money,sum+money[nowi])
            visited[nowi]=0
    # 방문을 안한경우
    dfs(visited,nowi+1,money,sum)


def isNearbyVisited(visited,index):
    global house_num
    left = index-1
    right = index +1
    if left<0 :
        left+=house_num
    if right>house_num-1:
        right-=house_num
    return visited[left] or visited[right]

dfs 로 모든 경우의 수를 탐색하는 방법이다.
2^n승에 가까운 시간복잡도를 가진다.
하지만 시간초과로 틀렷다...

두번째 코드

그 시점에서 최대의 갈수있는 최대의 값을 선택한다.