[C/C++] 코드업(codeup) 3703번 사탕 줍기 1

▽문제 바로가기

https://codeup.kr/problem.php?id=3703

사탕 줍기 1

---

입력

첫째 줄에 행의 수 N과 열의 수 M이 입력된다. (1<=N,M<=100)
둘째 줄부터 N+1행까지 맵의 정보가 입력된다. (숫자는 그 위치의 사탕 수를 의미한다.)

 

출력

가장 짧은 길로 가면서 얻을 수 있는 최대 사탕수를 출력한다.

 

문제 풀이

 

2차원 배열에서 지정된 위치(N, M)까지의 최단경로를 탐색하고 가장 큰 값을 찾는 문제입니다.

 

가장 짧은 길로 가야하므로 (0, 0)에서 시작한다면 맵의 하, 우 로만 움직일 수 있습니다.

 

또한, 가장 큰 값을 찾는 문제이므로 모든 경로를 탐색해야 합니다. 따라서, 매번 모든 경로의 최댓값을 계산할 수 없으므로 (0, 0)에서 (a, b)까지의 최댓값을 계산하여 저장하여 한 번만 계산할 수 있도록 메모이제이션 기법을 사용해야 합니다.

 

#include <stdio.h>

int memo[101][101];	//메모
int arr[101][101];	//맵
int n, m;

int myMax(int a, int b){
	if(a>b) return a;
	else return b;
}

int recur(int i, int j){
	//맵을 탈출하는 경우
	//(n, m)까지 탐색하겠다는 뜻
	if(i>=n||j>=m) return 0;
	
	//메모된 값이 있다면 함수호출하지 않고 메모된 값 리턴
	else if(memo[i][j]!=0) return memo[i][j];
	
	else return memo[i][j] = myMax(recur(i+1, j) + arr[i][j], recur(i, j+1) + arr[i][j]);
}

int main(){
	
	scanf("%d%d", &n, &m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	
	//(0, 0)에서 출발
	recur(0, 0);
	
	printf("%d", memo[0][0]);
	
	return 0;
}

 

메모 배열 memo[0][0]에 (0, 0)에서 출발하여 (n, m)까지의 최대 값이 저장되었습니다. 마찬가지로 메모배열 memo[0][1]에는 (0, 1)에서 (n, m)까지의 최댓값이 저장됩니다. memo[n-1][m-1]에 최대값이 저장되는 것이 아닙니다.