금광

출처:: Filpkart 인터뷰

분류:: dp

 

1. 문제 이해 및 해결과정

- 시작을 기준으로 하는 것이 아니라 들어오는 지점을 기준으로 생각을 전환해보자 - 예를 들면 (2.2)에서 갈 수 있는 곳은 (3,1) (3,2) (3,3) 이지만 (3,2)로 들어올 수 있는 것은 (2,1) (2,2) (2,3) 이 된다

 

2. 풀이방법

 1. dp

#금광
#
import sys
sys.stdin = open("input.txt","r")
t=int(input())

for tc in range(t):
    n,m=map(int,input().split())
    arr =list(map(int,input().split()))

    dp=[]
    index = 0
    for i in range(n):
        dp.append(arr[index:index+m])
        index+=m

    res=0
    for j in range(1, len(dp[i])):
        #시작점이 아니라 다음지점을 기준으로 생각하면 편리
        for i in range(n):
            if i==0: #오른쪽 위가 없음 즉, 왼쪽과 왼쪽대각선에서만 옴
                dp[i][j]+=max(dp[i][j-1],dp[i+1][j-1])
            elif i==n-1: #오른쪽 아래가 없음
                dp[i][j]+=max(dp[i-1][j-1],dp[i][j-1])
            else:
                dp[i][j]+=max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])

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

    print(res)

 

3. 오답원인

 

4. 알게된 점

- 다루어 본 적이 없는 입력이였다

- 이차원 배열(리스트)로 넣어야 하지만 리스트가 엔터 없이 한번에 입력된 경우 , 일단 입력을 모두 받은 후  다시 index를 이용하여 잘라서 넣자

arr =list(map(int,input().split()))
index = 0
    for i in range(n):
        dp.append(arr[index:index+m])
        index+=m