[dp기출] 금광

-정답 풀이:

하나의 위치는(i,j) 왼쪽(i,j-1), 왼쪽 위(i-1,j-1), 왼쪽 아래(i+1,j-1)의 숫자들로부터 온다. 그래서 이 숫자들 중에 최댓값을 (i,j)에 저장하면서 누적한다 

 

점화식

dp[i][j]=array[i][j] + max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])

t=int(input())
for _ in range(t):
	n,m=map(int,input().split())
    data=list(map(int,input().split()))
    dp=[[] for _ in range(n)]
    ans=0
    
    for i in range(n):
    	for j in range(i*m,(i+1)*m):
        	dp[i].append(data[j])
            
    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_up,left_down,left)
    
    for i in range(n):
        ans=max(ans,dp[i][m-1])                   
    print(ans)

 

-내 풀이

여기서 오류. 문제는 한 위치에서 오른쪽 위,옆,아래로만 이동할 수 있는데 내가 쓴 풀이로 하면 이 범주를 넘어가게 연산이 돼서 틀린 답이 출력된다 

따라서 점화식으로 진행해야한다 

t=int(input())
for _ in range(t):
	n,m=map(int,input().split())
    ans=0
    dp=[[] for _ in range(n)]
    data=list(map(int,input().split())
    cnt=0
    for i in range(n):
    	for j in range(i*m,(i+1)*m):
        	dp[i].append(data[j])
            
    for j in range(m):
    	  for i in range(n):
        	  cnt=max(dp[i][j],cnt)
          ans+=cnt
          cnt=0
        
    print(ans)