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

▽문제 바로가기

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

사탕 줍기 2

---

입력

첫 행에 격자판의 크기 N이 입력된다.(N<=10)

둘째 행부터 N+1행까지 격자판의 정보인 사탕수가 입력된다.

 

출력

지원이가 가질 수 있는 최대 사탕수를 출력한다.

 

문제 풀이

 

최대 사탕수를 출력해야 합니다. 모든 경우의 수를 탐색해야 하는데 입력 최대가 10이므로 10^10(백억)으로 매우 큰 수입니다.

 

따라서 완전 탐색을 하면서 불필요한 탐색을 줄일 필요가 있습니다.

예를 들어 N = 3이라고 가정합니다. 1행 1열을 선택하면 앞으로 1열은 선택할 수 없습니다.

따라서 1행 2행 3행을 (1-1-1), (1-1-2), (1-1-3)로 선택했다면 모두 선택할 수 없는 값입니다.

이때 3가지의 경우의 수를 줄이기 위해서 탐색을 끝내기 전에 (1-1-?) 2행의 선택이 겹칠때부터 탐색하지 않도록 해야 합니다.

 

따라서

1. 완전 탐색을 구현하면서

2. 불필요한 탐색을 줄이도록 하고

3. 불필요한 탐색을 줄이기 위해 경로를 저장해야합니다.

 

#include <stdio.h>

using namespace std;

int n;
int arr[11][11] = {0,};	//입력받을 배열
int cache[11] = {0,};	//경로를 저장하는 배열
int max = 0;

//필요한 탐색인가? 
bool isPromising(int row, int col){
	for(int i=0;i<row;i++){
		if(cache[i]==col+1) return false;
	}
	return true;
}

//백트래킹 완전탐색
void backtracking(int row, int sum){
	for(int i=0;i<n;i++){
		if(isPromising(row, i)){
			cache[row] = i+1;	//경로저장(1열 선택하면 1저장) 
			backtracking(row+1, sum+arr[row][i]);
		}
		else continue;
	}
	if(sum>max) max = sum;
}


int main(){
	
	scanf("%d", &n);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	 
	backtracking(0, 0);
	
	printf("%d", max);
	
	return 0;
}