[python] 백준 14430 - 자원 캐기

출처 : 백준, https://www.acmicpc.net/problem/14430

14430번: 자원 캐기

 

 

먼저, 생각해야 할 부분

 

1. 로봇이 움직일 수 있는 방향은 오른쪽과 아래 밖에 없다.

     어떤 칸에 도착했을 때 얻을 수 있는 자원의 최대 양은 어떤 것을 비교해야할까?

 

---

 

풀이

 

n, m = map(int, input().split())
blocks = [[0 for _ in range(m+1)]]

for _ in range(n):
  blocks.append([0] + list(map(int, input().split())))

for i in range(1, n+1):
  for j in range(1, m+1):
    blocks[i][j] = max(blocks[i-1][j], blocks[i][j-1]) + blocks[i][j]

print(blocks[i][j])

 

로봇은 오른쪽과 아래쪽으로만 움직일 수 있으므로,

현재칸 기준으로 위쪽과 왼쪽의 칸 중 각 칸까지 올 때까지 캔 자원의 값을 비교하여 큰 값을 고르고

현재 칸에 자원이 있다면 +1을 해준 값을 내 칸에 넣어준다.

 

---

시간 복잡도

O(N*M)

 

알게 된 점

 

-

 

고찰

 

-

 

Github

백준 14430 - 자원 캐기