멤고리즘 2회 3번. 산삼 찾기(DP)

유정이의 산삼

문제

N * N 크기의 숲이 있다. 이 숲에는 1000년 묵은 산삼이 군데군데 자라고 있어서 유정이는 익균이의 자동차를 타고 산삼을 먹으려 한다.

익균이의 자동차는 (1, 1)의 위치에서 출발하여 (N, N)까지 이동하는데, 익균이의 자동차는 고물이라 오른쪽 또는 아래쪽으로밖에 움직이지 못한다. 유정이는 무한한 양의 산삼을 먹을 수 있다고 가정(?)하자.

익균이의 자동차를 이용해 유정이가 최대한 많이 산삼을 먹도록 하는 프로그램을 작성하시오. 

입력

첫 줄에는 숲의 크기 N (3 <= N <= 100)이 주어진다.

둘째줄부터는 주어진 지도가 N줄 만큼 입력된다. (단, 0은 산삼 없음, 1은 산삼 있음을 의미한다.)

출력

유정이가 먹을 수 있는 최대 산삼의 양을 출력한다.

예제 입력

5
0 1 0 0 1
0 0 1 0 0
1 0 1 1 0
1 1 0 1 0
1 0 0 0 1

예제 출력

6

---

[문제 설명]

(이런 문제의 경우, 손으로 직접 예제를 풀어보면서 문제를 이해하시는 게 제일 도움이 됩니다.)

문제에서 오른쪽 또는 아래쪽으로만 움직일 수 있고, 움직이면서 최대한 많이 산삼을 먹는게 목표인데요.

즉, 오른쪽 또는 아래쪽으로 이동해보면서 1을 가장 많이 지나는 경우를 찾으시면 됩니다.

[소스코드 설명]

저같은 경우 배열을 (1, 1)부터 사용을 하기 위해서 배열 사이즈를 하나 더 늘려주고, 처음에{0, 0}으로 초기화를 하였습니다. 이렇게 하시면은 비교를 할 때 맵의 크기를 넘어가는 경우에 대해서도 예외처리를 안해도 되기 때문에 매우 편합니다.

제가 짠 코드를 디버깅 돌려보면 다음과 같은 결과가 나옵니다.

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	1	1	1	2
2	0	0	1	2	2	2
3	0	1	1	3	4	4
4	0	2	3	3	5	5
5	0	3	3	3	5	6

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <iostream> #define MAX 101   using namespace std;   int main() {     int N;     int arr[MAX][MAX]={{0, 0}, };       cin >> N;       for(int i=1; i<=N; i++)     {         for(int j=1; j<=N; j++)             cin >> arr[i][j];     }       for(int i=1; i<=N; i++)     {         for(int j=1; j<=N; j++)         {             if(arr[i][j-1] > arr[i-1][j])                 arr[i][j] += arr[i][j-1];             else                 arr[i][j] += arr[i-1][j];                          //cout << arr[i][j] << " ";         }         //cout << endl;     }       cout << arr[N][N];       return 0; }