완전탐색 연습문제 (C++)

[풀이]

n개 자연수 중 r개를 고르는 조합 문제이지만 nCr에서 r의 모든 경우의 수를 고려해야 하는 문제이다.

따라서 각 숫자가 포함되냐, 아니냐 두 가지 경우로 나눠 2^n 개의 경우의 수를 고려하는 문제로 바꿔 생각할 수 있다.

 

예를 들어, n=3이고 {1,2,3}을 고려해야하는 문제라면 3C0, 3C1, 3C2, 3C3 네 가지 경우를 모두 고려해야 하며 해당 경우의 수는 모두 1+3+3+1 = 8가지인데, 각각을 포함되냐 포함되지 않냐로 구해도 마찬가지로 2^3 = 8가지 이다.

이를 재귀함수를 이용해 구현하면 다음과 같다.

vector<int> v;
int n, ret;

void go(int idx, int sum) {
	if (idx == n){
		ret = max(ret, sum%11);
		return;
	}
	go(idx+1, sum+v[idx]); // 포함O
    go(idx+1, sum); // 포함X
}

int main(){
	cin >> n;
	for(int i=0; i<n; i++) {
		int tmp; cin >> tmp;
		v.push_back(tmp);
	}
	go(0, 0);
	cout << ret;
	return 0;
}

 

위와 같은 백트래킹 코드에서 불필요한 가지를 쳐내는 과정을 가지치기라고 하는데,

만약 11로 나눈 나머지가 10이 나오는 경우는 해당 프로그램을 종료해도 되므로

11로 나눈 나머지가 10인 경우를 조건으로 추가해주면 실행 속도가 증가할 수 있다.