굳건하게

문제 : https://www.acmicpc.net/problem/17436

[알고리즘풀이]

N개의 소수를 p1, p2, ⋯ pn 이라고 하자.

그리고 1 ~ M 이하의 자연수 중에서 p1으로 나눠지는 수들의 집합을 P1, ⋯ pn으로 나눠지는 수들의 집합을 Pn 이라고 한다면, 우리가 구하고 싶은 답은 n(P1 U P2 U ⋯ U Pn)이 될 것이다. ( 합집합의 원소의 개수 )

n(P1 U P2 U ⋯ U Pn)

=+n(P1) + n(P2) + ⋯ + n(Pn)

  -n(P1 ∩ P2) -n(P1 ∩ P3) - ⋯ - n(Pn-1 ∩ Pn)

  +n(P1 ∩ P2 ∩ P3) + ⋯ + n(Pn-2 ∩ Pn-1 ∩ Pn)

  - ⋯

  (-1)^(n-1) * n(P1 ∩ P2 ∩ ⋯ ∩Pn)

이고 모두 소수이므로 서로소 성질에 의해 n(Pi ∩ Pj) = M / (Pi * Pj) 가 성립한다.

따라서, 백트레킹 기법을 활용해 위의 공식을 계산해주면 된다.

#include<iostream>
#include<vector>

using namespace std;

long long answer, m;
int n, p[10];

void bt(int, int, int, vector<int>);

int main(void){
	cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++){
        // i 개씩 뽑을거야. 안겹치게 오름차순으로
        for(int j = 1; j <= n; j++){
            vector<int> v;
            v.push_back(j);
            bt(1, j, i, v);
            v.pop_back();
        }
    }
    cout << answer;
}

void bt(int size, int start, int l, vector<int> v){
    if(size == l){
    	if(l % 2 == 1){
            long long temp = 1;
            for(int i = 0; i < l ; i++){
                temp *= p[v[i] - 1];
            }
            answer += m / temp;
        }
        else{
            long long temp = 1;
            for(int i =0; i < l; i++)
                temp *= p[v[i] - 1];
            answer -= m / temp;
        }
        return;
    }
    for(int i = start + 1; i <= n; i++){
        v.push_back(i);
        bt(size + 1,i,l,v);
        v.pop_back();
    }
}

문제 : https://www.acmicpc.net/problem/9663

[알고리즘풀이]

큰 틀은 백트레킹 기법을 이용해서 Row마다 가능한 모든 자리에 Queen을 세워보는 것이다.

vector<int> v 에는 지금까지 Queen을 세운 자리가 저장되어있다.

ex) v[0] = 1 이라면 0번째 row, 1번째 column에 Queen을 세웠다.

i번 째 row에 Queen을 세우는 방법은 그동안 0 ~ (i - 1)번 째 row에 세워둔 Queen들과 같은 열이 아니고, 대각선 상에 위치하지 않으면 된다. 따라서 같은 열이 아닌지, 오른쪽 아래로 내려가는 대각선 상에 있지 않은지, 왼쪽 아래로 내려가는 대각선 상에 있지 않은지 Check해서 모두 통과한다면 그 자리에는 Queen을 세울 수 있다.

#include<iostream>
#include<vector>

using namespace std;

int n, c;

void bt(int, vector<int>);

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		vector<int> v; // v에는 열을 넣는다.
		v.push_back(i);
		bt(1,v);
		v.pop_back();
	}
	cout << c;
}

void bt(int row, vector<int> v) {
	if (row == n ) {
		c++;
		return;
	}
	for (int i = 0; i < n; i++) {
		// 같은열을 체크하자.
		bool check1 = false;
		for (int j = 0; j < row; j++)
			if (i == v[j]) {
				check1 = true;
				break;
			}
		if (check1)
			continue;
		// 오른쪽 대각선을 체크하자.
		bool check2 = false;
		for (int j = 0; j < row; j++) {
			if (i == v[j] + (row + 1) - (j + 1)) {
				check2 = true;
				break;
			}
		}
		if (check2)
			continue;
		// 왼쪽 대각선을 체크하자.
		bool check3 = false;
		for (int j = 0; j < row; j++) {
			if (i == v[j] - (row + 1) + (j + 1)) {
				check3 = true;
				break;
			}
		}
		if (check3)
			continue;
        // 다 통과하면 Queen을 세워보자.
		v.push_back(i);
		bt(row + 1, v);
		v.pop_back();
	}
}

문제 : https://www.acmicpc.net/problem/15652

[알고리즘풀이]

중복은 허용되지만, 오름차순으로 뽑아야하므로 가장 마지막에 담긴 원소를 넘겨주며 백트레킹 기법을 구현한다.

#include<iostream>
#include<vector>

using namespace std;

int m, n;

void bt(int, int, vector<int>);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		vector<int> v;
		v.push_back(i);
		bt(1, i, v);
		v.pop_back();
	}
}

void bt(int count, int start, vector<int> v) {
	if (count == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int k = start; k <= n; k++) {
		v.push_back(k);
		bt(count + 1, k, v);
		v.pop_back();
	}
}

문제 : https://www.acmicpc.net/problem/15651

[알고리즘풀이]

중복이 허용되고, 오름차순도 지킬 필요가 없으므로 그냥 조건 없는 백트레킹을 구현한다.

#include<iostream>
#include<vector>

using namespace std;

int m, n;

void bt(int, vector<int>);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		vector<int> v;
		v.push_back(i);
		bt(1, v);
		v.pop_back();
	}
}

void bt(int count, vector<int> v) {
	if (count == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int k = 1; k <= n; k++) {
		v.push_back(k);
		bt(count + 1, v);
		v.pop_back();
	}
}