[백준BaekJoon]14430: 자원 캐기/C++

문제

인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라!

---

코드

DP문제이다.

#include <bits/stdc++.h> 
using namespace std;

int board[301][301] = { 0, };
int DP[301][301] = { 0, };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++)cin >> board[i][j];
	}

	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			DP[i][j] = max(DP[i - 1][j] + board[i][j], DP[i][j - 1] + board[i][j]);
		}
	}
	cout << DP[N][M];
}

각 칸마다 왼쪽에서 오른쪽으로, 위에서 아래로 두가지 경우가 발생한다. 

두 경우 중 누적값이 큰 값을 갱신해주면 된다.

 

끝. 후딱 풀었음