[백준] 자원 캐기 (14430번)

난이도 : Silver2
Link : https://www.acmicpc.net/problem/14430
Tag : 다이나믹 프로그래밍
풀이일자 : 2024년 9월 14일

📌 문제 탐색하기

N,M : 탐색할 자원의 크기
본 문제는 오른쪽으로 이동하거나, 아랫쪽으로 이동하는 로봇이 최대로 탐색할 수 있는 자원의 개수를 구하는 문제이다.

가능한 시간복잡도

탐색할 자원의 크기는 N x M 이므로 탐색할 수 있는 시간복잡도는 O(n*m)으로 생각 할 수 있다.

📌 문제 접근 방법

BFS 문제와 비슷하지만 지나는 경로마다 최대치를 계산하고 해당 좌표에 지금까지 얻은 자원의 갯수를 넣는다면 마지막 좌표에서 최대값이 들어있을것으므로 DP문제로 접근 할 수 있다.

따라서 x축으로 이동할때와 y축으로 이동할 때의 최대값을 해당 좌표에 넣어주면 될것이다.

📌 코드 설계하기

1. n,m을 입력 받는다.
2. grid를 생성한다 (n x m 크기의 자원 맵)
3. dp 배열을 생성한다 (grid를 탐색하면서 지금까지 모은 자원을 저장할 공간)
4. 2차원배열을 탐색하며 dp좌표에 전 좌표에서 x축 y축 이동중 큰 값을 저장한다.
5. dp의 마지막 좌표를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n,m = map(int,input().split())
grid = [list(map(int,input().split())) for i in range(n)]
dp = [[0 for i in range(m+1)]for j in range(n+1)]


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

print(dp[-1][-1])