백준 11048 [C++]

www.acmicpc.net/problem/11048

11048번: 이동하기

1. 풀이방법

 

- 다이나믹프로그래밍을 이용해서 탑다운 방식으로 해결하였습니다.

 

- 저 같은 경우 1행의 모든 값과 1열의 모든 값들은 가로 또는 세로로 쭉 이동하는 경우밖에 없으므로

 

- 초기화할 때 먼저 쭉 작업을 해서 dp 테이블에 넣어놓은 후 시작하였습니다.

 

 

 

 

 

2. 주의사항

 

- 주의사항은 아니고 풀고난 후에 생각난 건데 얻을 수 있는 최대의 사탕의 수를 구하는 것이므로

 

- 대각선 이동은 빼도 될 것 같습니다.

 

- 사탕을 뺏어간다는 조건이 있지 않은 이상 대각선이 가로->세로, 또는 세로->가로 로 이동하는 것 보다 많은 사탕을 얻을 수는 없기 때문에 사실 확인하지 않아도 될 것입니다.

 

 

 

 

3. 나의코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int N, M;
int candymap[1001][10001];
int dp[1001][1001];

void inputs() {//기본셋팅
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> candymap[i][j];
			dp[i][j] = -1; //dp테이블은 -1로 초기화
		}
	}
	dp[1][1] = candymap[1][1];
	for (int i = 2; i <= N; i++) {
		dp[i][1] = dp[i - 1][1]+candymap[i][1];
	}
	for (int j = 2; j <= N; j++) {
		dp[1][j] = dp[1][j-1]+candymap[1][j];
	}
}
int maxthree(int num1, int num2, int num3) {
	int tmp = max(num1, num2);
	tmp = max(tmp, num3);
	return tmp;
}
int getdp(int x, int y) {
	if (dp[x][y] != -1) return dp[x][y];
	else {
		dp[x][y] = maxthree(getdp(x - 1, y), getdp(x, y - 1), getdp(x - 1, y - 1))+candymap[x][y];
		return dp[x][y];
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	cout << getdp(N,M) << "\n";
	return 0;
}