[BOJ 6192 // C++] Cow Pie Treasures

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6192번 문제인 Cow Pie Treasures이다.
문제는 아래 링크를 확인하자.

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

6192번: Cow Pie Treasures

(1,1)에서 출발해 (R,C)까지 이동할 때 가장 많은 금화를 모을 수 있는 경로를 찾는 문제이다.

 

(1,1)에서 출발해 (r,c)까지 이동하는 방법은 (r-1,c-1)을 경유하거나 (r,c-1)을 경유하거나 (r+1,c-1)을 경유하는 세 가지가 존재한다. 각 방법마다 해당 칸까지 이동하면서 모을 수 있는 금화의 최댓값을 비교해 (r,c)까지 이동하면서 모을 수 있는 금화 개수의 최댓값을 dp로 구해나가는 것으로 문제를 해결하자.

 

(1,1)에서 출발해 경유할 수 없는 칸((2,1) 등)에서 금화를 주워 최적의 경로를 잘못 구하는 일이 일어나지 않게끔 구현에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C;

int coins[102][101];
int dp[102][101];

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) cin >> coins[r][c];
	}

	dp[1][1] = coins[1][1];

	for (int c = 2; c <= C; c++) {
		for (int r = 1; r <= R; r++) {
			for (int dr = -1; dr < 2; dr++) {
				dp[r][c] = max(dp[r][c], dp[r + dr][c - 1]);
			}
			if (dp[r][c]) dp[r][c] += coins[r][c];
		}
	}

	cout << dp[R][C];
}