백준 14430 자원 캐기 c++

https://www.acmicpc.net/problem/14430

14430번: 자원 캐기

문제 보자마자 dfs로 풀었다. 결과는 바로 시간 초과 col 300 row 300이라 dfs로 안되는걸 알았어야 했는데;;

// 자원 캐기
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > board;
int col, row, res;

void dfs(int x, int y, int cnt) {
	if (x == col - 1 && y == row - 1) {
		res = max(res, cnt);
		return ;
	}
	if (x + 1 < col)
		dfs(x + 1, y, cnt + board[x + 1][y]);
	if (y + 1 < row)
		dfs(x, y + 1, cnt + board[x][y + 1]);
}


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

	cin >> col >> row;
	board = vector(col, vector(row, 0));
	for (int i = 0; i < col; i++)
		for (int j = 0; j < row; j++)
			cin >> board[i][j];
	dfs(0, 0, 0);
	cout << res;
}

dfs가 시간 초과면 그리디 아니면 dp인데 이건 그리디로 도저히 생각이 안났다.

그럼 뭐 dp겠지...

근데 일반적인 dp와 달리 2차원배열로 dp테이블 만들어야 해서 골이 아팠다.

근데 이동 방향이 아래, 오른쪽이니 두 방향 번갈아가면서 dp테이블 만들면 된다.

풀고 나니 중복로직이 좀 거시기 하긴 하지만 코테니까요~

// 자원 캐기
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > board;
vector<vector<int> > dp;
int col, row, res;

void goDown(int x, int y) {
	for (; x < col; x++)
	{ // 중복로직이긴 한데 코테는 빨리 풀면 장땡이니까요 ㅎ
		int prev1 = 0, prev2 = 0;
		if (x - 1 >= 0)
			prev1 = dp[x - 1][y];
		if (y - 1 >= 0)
			prev2 = dp[x][y - 1];
		dp[x][y] = max(prev1, prev2) + board[x][y];
	}
}
void goRight(int x, int y) {
	for (; y < row; y++)
	{
		int prev1 = 0, prev2 = 0;
		if (x - 1 >= 0)
			prev1 = dp[x - 1][y];
		if (y - 1 >= 0)
			prev2 = dp[x][y - 1];
		dp[x][y] = max(prev1, prev2) + board[x][y];
	}
}

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

	cin >> col >> row;
	board = vector(col, vector(row, 0));
	dp = vector(col, vector(row, 0));

	for (int i = 0; i < col; i++)
		for (int j = 0; j < row; j++)
			cin >> board[i][j];

	for (int dist = 0; dist < min(col, row); dist++) {
		goDown(dist, dist);
		goRight(dist, dist);
	}

	cout << dp[col - 1][row - 1];
}