N과 M

with MK·2020년 7월 15일
알고리즘
0

알고리즘

목록 보기
4/12
post-thumbnail

https://www.acmicpc.net/problem/15649
N과 M (1)

#include <iostream>
using namespace std;

bool check[10];
int a[10];

void go(int index, int n, int m) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << a[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (check[i]) continue;
		check[i] = true;
		a[index] = i;
		go(index + 1, n, m);
		check[i] = false;
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	go(0, n, m);
	return 0;
}

https://www.acmicpc.net/problem/15650
N과 M (2)

#include <iostream>
using namespace std;

int a[10];

void go(int index, int start, int n, int m) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << a[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = start; i <= n; i++) {
		a[index] = i;
		go(index + 1, i + 1, n, m);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	go(0, 1, n, m);
	return 0;
}

https://www.acmicpc.net/problem/15651
N과 M (3)
같은 수를 여러번 골라도 된다.

#include <iostream>
using namespace std;

int a[10];

void go(int n, int m, int index) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << a[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		a[index] = i;
		go(n, m, index + 1);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	go(n, m, 0);
	return 0;
}

함수 정의할 때, return 깜빡하지 마라 종료 조건

https://www.acmicpc.net/problem/15652
N과 M (4)
같은 수를 여러 번 골라도 되며, 비내림차순이어야 한다.

#include <iostream>
using namespace std;

int a[10];

void go(int n, int m, int index, int start) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << a[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = start; i <= n; i++) {
		a[index] = i;
		go(n, m, index + 1, i);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	go(n, m, 0, 1);
	return 0;
}

https://www.acmicpc.net/problem/15654
N과 M (5)

N개의 자연수가 주어졌을 때, 길이가 M인 수열을 모두 구하라

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int check[10];
int d[10];

void go(int n, int m, int index) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
        return;
	}
	for (int i = 0; i < n; i++) {
		if (check[i]) continue;
		check[i] = true;
		d[index] = a[i];
		go(n, m, index + 1);
		check[i] = false;
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	go(n, m, 0);
	return 0;
}

https://www.acmicpc.net/problem/15655
N과 M (6)
오름차순 수열

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int check[10];
int d[10];

void go(int n, int m, int index, int start) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
        return;
	}
	for (int i = start; i < n; i++) {
		if (check[i]) continue;
		check[i] = true;
		d[index] = a[i];
		go(n, m, index + 1, i + 1);
		check[i] = false;
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	go(n, m, 0, 0);
	return 0;
}

https://www.acmicpc.net/problem/15656
N과 M (7)

같은 수를 여러 번 골라도 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int d[10];

void go(int n, int m, int index) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		d[index] = a[i];
		go(n, m, index + 1);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	go(n, m, 0);
	return 0;
}

https://www.acmicpc.net/problem/15657
N과 M (8)
(7) + 비내림차순

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int d[10];

void go(int n, int m, int index, int start) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = start; i < n; i++) {
		d[index] = a[i];
		go(n, m, index + 1, i);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	go(n, m, 0, 0);
	return 0;
}

https://www.acmicpc.net/problem/15663
N과 M (9)

중복된 수 들이 주어진다.

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int cnt[10];
int d[10];

void go(int n, int m, int index) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (cnt[i] > 0) {
			cnt[i] -= 1;
			d[index] = a[i];
			go(n, m, index + 1);
			cnt[i] += 1;
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	int temp[10];
	for (int i = 0; i < n; i++) {
		cin >> temp[i];
	}
	sort(temp, temp + n);
	int k = 0;
	int x = temp[0];
	int c = 1;
	for (int i = 1; i < n; i++) {
		if (x == temp[i])
			c += 1;
		else {
			a[k] = x;
			cnt[k] = c;
			k += 1;
			x = temp[i];
			c = 1;
		}
	}
	a[k] = x;
	cnt[k] = c;
	n = k + 1;
	go(n, m, 0);
	return 0;
}

erase 함수를 사용하는 경우

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a[10];
int num[10];
int c[10];
vector<vector<int>> d;
void go(int index, int n, int m) {
    if (index == m) {
        vector<int> temp;
        for (int i=0; i<m; i++) {
            temp.push_back(num[a[i]]);
        }
        d.push_back(temp);
        return;
    }
    for (int i=0; i<n; i++) {
        if (c[i]) continue;
        c[i] = true;
        a[index] = i;
        go(index+1, n, m);
        c[i] = false;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        cin >> num[i];
    }
    sort(num,num+n);
    go(0,n,m);
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(),d.end()),d.end());
    for (auto &v : d) {
        for (int i=0; i<m; i++) {
            cout << v[i];
            if (i != m-1) {
                cout << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

https://www.acmicpc.net/problem/15664
N과 M (10)
(9) + 비내림차순

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int cnt[10];
int d[10];

void go(int n, int m, int index, int start) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = start; i < n; i++) {
		if (cnt[i] > 0) {
			cnt[i] -= 1;
			d[index] = a[i];
			go(n, m, index + 1, i);
			cnt[i] += 1;
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	int temp[10];
	for (int i = 0; i < n; i++) {
		cin >> temp[i];
	}
	sort(temp, temp + n);
	int k = 0;
	int x = temp[0];
	int c = 1;
	for (int i = 1; i < n; i++) {
		if (x == temp[i])
			c += 1;
		else {
			a[k] = x;
			cnt[k] = c;
			k += 1;
			x = temp[i];
			c = 1;
		}
	}
	a[k] = x;
	cnt[k] = c;
	n = k + 1;
	go(n, m, 0, 0);
	return 0;
}

https://www.acmicpc.net/problem/15665
N과 M (11)
같은 수를 여러번 골라도 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int cnt[10];
int d[10];

void go(int n, int m, int index) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (cnt[i] > 0) {
			d[index] = a[i];
			go(n, m, index + 1);
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	int temp[10];
	for (int i = 0; i < n; i++) {
		cin >> temp[i];
	}
	sort(temp, temp + n);
	int k = 0;
	int x = temp[0];
	int c = 1;
	for (int i = 1; i < n; i++) {
		if (x == temp[i])
			c += 1;
		else {
			a[k] = x;
			cnt[k] = c;
			k += 1;
			x = temp[i];
			c = 1;
		}
	}
	a[k] = x;
	cnt[k] = c;
	n = k + 1;
	go(n, m, 0);
	return 0;
}

https://www.acmicpc.net/problem/15666
N과 M (12)
(11) + 고른 수열은 비내림차순이어야 한다.

#include <iostream>
#include <algorithm>
using namespace std;

int a[10];
int cnt[10];
int d[10];

void go(int n, int m, int index, int start) {
	if (index == m) {
		for (int i = 0; i < m; i++) {
			cout << d[i];
			if (i != m - 1) cout << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = start; i < n; i++) {
		if (cnt[i] > 0) {
			d[index] = a[i];
			go(n, m, index + 1, i);
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	int temp[10];
	for (int i = 0; i < n; i++) {
		cin >> temp[i];
	}
	sort(temp, temp + n);
	int k = 0;
	int x = temp[0];
	int c = 1;
	for (int i = 1; i < n; i++) {
		if (x == temp[i])
			c += 1;
		else {
			a[k] = x;
			cnt[k] = c;
			k += 1;
			x = temp[i];
			c = 1;
		}
	}
	a[k] = x;
	cnt[k] = c;
	n = k + 1;
	go(n, m, 0, 0);
	return 0;
}
profile
with MK
SS
이전 포스트

비트마스크

다음 포스트

그래프

0개의 댓글