[알고리즘 스터디] 5주차

이것이 코딩테스트다 #31

오른쪽위, 오른쪽 아래, 오른쪽 방향을 나타내는 dx,dy배열을 만든 후 3가지 방향을 깊이 우선 탐색으로 탐색하여 y==4의 위치 일때의 값들을 비교하여 최댓값인 것을 반환 하려고 하였다..

다이나믹이 아닌 dfs로 접근했다,, 아마 시간복잡도가 엄청날 것으로 예상된다,,
또한,,, 테스트케이스도 하나밖에 통과하지 못했다..

n,m= map(int,input().split())
arr=list(map(int,input().split()))

graph=[]
dx=[-1,1,0]
dy=[1,1,1]
#d=[[0]*n for _ in range(m)]

for i in range(0,len(arr),m):
    graph.append(arr[i:m+i])

print(graph)
#d[0][0]=graph[0][0]

answer=0

def dfs(x,y,result):
    global answer
    

    for j in range(3):
        nx=x+dx[j]
        ny=y+dy[j]
       
        
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        
        #print(nx,ny,result+graph[nx][ny])  
        if ny==3:
            
            answer=max(result+graph[nx][ny],answer)
            print(nx,ny,answer)  


        
        else:
           
            dfs(nx,ny,result+graph[nx][ny])
       
        
    return answer

temt=0
for k in range(n):
    print( k,dfs(k,0,0),graph[k][0], end=",")

    temt=max(dfs(k,0,0)+graph[k][0],temt)

print(temt)




     

왜 잘못되었는지 아직 찾지 못했다... 다시 공부하기

답안

---

다이나믹 프로그래밍이 아직 익숙하지 않아 다시 공부해야한다..

(1) 다이나믹 프로그래밍: 한번 해결된 부분 문제의 정답을 메모리에 기록하여, 한번 계산한 답은 다시 계산하지 않도록 하는 문제해결 기법

=>점화식을 세워서 코드로 옮겨야한다

2차원 dp테이블에 가장 많은 금을 가지고 있는 경우를 저장
현재 시점을 기준으로 왼쪽 아래, 왼쪽 위, 왼쪽 세방향에서 온 것 중에 가장 큰 값을 dp테이블에 저장한다.

n,m= map(int,input().split())
arr=list(map(int,input().split()))

dp=[]

for i in range(0,len(arr),m):
    dp.append(arr[i:m+i])


 #y=0인 열 제외하고 탐색   
for j in range(1,m):
    for i in range(n):
         #왼쪽 위
        if i==0:
            left_up=0
        else:
            left_up=dp[i-1][j-1]
         #왼쪽 아래   
        if i==n-1:
            left_down=0
        else:
            left_down=dp[i+1][j-1]
        #왼쪽
        left=dp[i][j-1]
        dp[i][j]=dp[i][j]+max(left,left_down,left_up)

result=0
for i in range(n):
    result=max(result,dp[i][m-1])

print(result)

처음 했던 방법에서 내가 각 테이블에 값을 저장하지 않으려는 이유가 계속 최댓값으로 업데이트한다면 수가 계속 커질 것이라고 생각 했기 때문이다
이 방법으로도 한번 풀어보자,,, 난 빡대가리니까,,,