금광

30 1초  128MB

nXm크기 금광에서 첫번째 열부터 시작해서 m번에 걸쳐 오른쪽 위, 오른쪽, 오른쪽 아래 중 하나의 위치로 이동가능

금의 최대 크기 출력프로그램 작성하기.

---

조건:

1번째줄에 테스트 케이스T 입력.

테스트 케이스 첫째줄에 n,m 공백으로 구분하여 입력.

둘째 줄에 nxm개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됨.

테스트 케이스마다 금의 최대 크기 출력.

 

#테스트 케이스 입력
for tc in range(int(input()) ):
#금광 정보 입력
n,m=map(int,input().split())
#초기 금광 정보
array=list(map(int,input().split() ))

 

핵심키워드 : 2차원 리스트로 해결하기.

기존의 초기 값들을 전부 리스트에 집어넣고 시작해야 될거 같았다.

 

막혔던 부분 :

리스트로 한줄에 받는것 까진 했는데, 그걸 2차원 테이블로 만드는 방법을 몰랐고,

점화식 및 경우의 수를 나누는걸 생각하지 못했다.

 

 

해결 방법:

초기 금광 값을 2차원 테이블에 각각 저장한다.

금광의 모든 위치에서 왼쪽 위, 왼쪽, 왼쪽아래 3가지 경우중 금이 가장 많은 경우를 테이블에 저장해준다.(갱신함)

dp테이블에 초기값을 바로 담는다. 편의상으로

 

제약조건으로 리스트 범위를 벗어나는 경우에는 0으로 간주하도록 한다.

 

점화식 : dp[i][j]=array[i][j]+max(dp[i-1][j-1] , dp[i][j-1] , dp[i+1][j-1]) 

 

 

 

해설

#테스트 케이스 입력
for tc in range(int(input()) ):
 #금광 정보 입력
 n,m=map(int,input().split())
 #초기 금광 정보
 array=list(map(int,input().split() ))

 #2차원 dp테이블 초기화
 dp=[]
 index=0
 #인덱스 슬라이싱을 통해 index+m-1번째 까지의 원소까지 한행에 입력받아서 2차원 테이블을 만들어 낸다.
 for i in range(n):
   dp.append(array[index:index+m])
   index+=m

 #다이나믹 프로그래밍 실행
 #첫번째행인 0열은 시작지점이니 그대로 두고 1번째 열부터 m-1번째 열까지 진행하고
 #행은 0부터 시작해서 n-1열까지 진행한다.
 for j in range(1,m):
   for i in range(n):
   #1.왼쪽 위일 때
   #행이 0이면 왼쪽위가 없으므로 0
   if i==0:
   left_up = 0
   else:
   left_up=dp[i-1][j-1]
   # 2.왼쪽 아래일 때
   # 행이 n-1이면 왼쪽아래가 없으므로 0
   if i == n-1:
   left_down = 0
   else:
   left_down = dp[i+1][j-1]
   # 3.왼쪽에서 왔을 때
   left=dp[i][j-1]
   dp[i][j]=dp[i][j]+max(left_up,left,left_down)

   result=0
   #마지막 행의 열들 중 제일 큰 값이 최대값이 된다.
   for i in range(n):
     result=max(result, dp[i][m-1])
     print(result)

 

 

 

2차원 테이블로 저장하는 방법

1. array=list( map( int, input().split() ) ) 으로 한데 모아 전부 저장.

2.

 dp를 선언하고 행의 개수(n) 만큼 슬라이싱을 통해 0~m-1번째 원소씩 끊어서 각각 행에 넣어주면 된다.

   dp=[]

   index=0

   for i in range(n):

     dp.append( array[index:index-m]    )

     index+=m