[FlipKart 인터뷰] 금광

 

 

초기접근

---

점화식 세우는 과정은 어렵지 않았다.

 

각 단계는 전 단계에서 올 수 있는 경우중에 가장큰 수 + 해당 금광수 이다.

이것을 점화식으로 나타내면

 

d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j]

이다.

 

여기서 가장 위쪽과 아래쪽은 전단계에서 오는 경우의 수가 1개가 적다.

이것을 따로 구현하는 것 보다 data와 d 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다.

 

 

 

 

해결 아이디어

---

1. 점화식 : d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j]

2. 쉽게 구현하기 : 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다.

 

 

 

 

정답코드

---

tc = int(input())
for t in range(tc):
    n, m = map(int, input().split())
    temp_data_list = list(map(int, input().split()))
    temp_count = 0
    data = [[0] * (m+1) for _ in range(n+2)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            data[i][j] = temp_data_list[temp_count]
            temp_count += 1

    d = [[0] * (m+1) for _ in range(n+2)]

    d[1][1] = data[1][1]
    d[2][1] = data[2][1]
    d[3][1] = data[3][1]
    maxList = []
    for j in range(2, m+1):
        for i in range(1, n+1):
            d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j]
            if j == m:
                maxList.append(d[i][j])
    print(max(maxList))