https://www.acmicpc.net/problem/1759

 

1759번: 암호 만들기

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

www.acmicpc.net

 

C개의 수를 입력받아서 길이 L의 수열을 출력하면 된다.

 

입력은 소문자로만 들어오고, 정렬되어서 들어오지 않는다.

 

출력되는 수열은 오름차순 정렬 상태여야 하기 때문에 입력을 받은 이후에 정렬이 필요하다. 그리고 사전순의 상태를 유지하기 위해서 st라는 변수를 두어서 이전에 사용된 문자의 인덱스를 관리한다.

 

문자의 길이가 0이 되면 이 전에 사용한 문자의 인덱스가 존재하지 않기 때문에 0으로 처리해준다.

 

문자를 중복해서 사용할 수 없기 때문에 특정 인덱스의 문자가 사용중인지 여부를 판단하는 배열이 필요하다.

 

 

출력되는 문자열의 문자 사이사이에 공백이 당연히 포함된다고 생각해서 공백까지 출력해서 맞왜틀을 반복했다.

 

출력 형식을 잘 확인하도록 하자.

 

#include<iostream>
#include<algorithm>
using namespace std;
int L, C, st;
char n[15], arr[15];
bool isused[15];
bool Check() {
	int cntM = 0, cntJ = 0;
	for (int i = 0; i < L; i++) {
		if (arr[i] == 'a' or arr[i] == 'e' or
			arr[i] == 'i' or arr[i] == 'o' or arr[i] == 'u')
			cntM++;
		else
			cntJ++;
	}
	if (cntM >= 1 && cntJ >= 2) //모음1, 자음2개가 있어야 true
		return true;
	else
		return false;
}
void func(int k) {
	if (k == L) {
		if (Check()) {
			for (int i = 0; i < L; i++)
				cout << arr[i];
			cout << '\n';
		}
		return;
	}
	if (k == 0) st = 0;
	for (int i = st; i < C; i++) {
		if (!isused[i]) {
			arr[k] = n[i];
			isused[i] = true;
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> L >> C;
	for (int i = 0; i < C; i++)
		cin >> n[i];
	sort(n, n + C);
	
	func(0);
	return 0;
}

https://www.acmicpc.net/problem/15666

 

 

15666번: N과 M (12)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

사용했던 숫자를 여러 번 사용할 수 있다.

 

따라서 숫자 사용 여부를 관리하는 배열이 필요하지 않다.

 

수열을 벡터에 쌓고, 원하는 길이만큼 쌓이면 set에 넣고 벡터를 비워주는 것을 반복한다.

 

set에는 중복되는 원소가 들어갈 수 없다는 것을 활용했다.

 

 

 

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, num[8], arr[8], Start;
set<vector<int> > st;
void func(int k) {
	if (k == m) {
		vector<int> v;
		for (int i = 0; i < m; i++)
			v.push_back(arr[i]);
		st.insert(v);
		v.clear();
		return;
	}
	if (k == 0) Start = 0;
	for (int i = Start; i < n; i++) {
		arr[k] = num[i];
		Start = i;
		func(k + 1);
	}

}
int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	func(0);
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/15665

 

15665번: N과 M (11)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

 

숫자의 입력이 중복되어서 들어올 수 있다.

 

결과로 나오는 수열은 오름차순으로 정렬되는 상태여야 한다. 하지만 입력은 정렬되어서 들어오는 것이 아니기 때문에 입력을 모두 받은 이후에 오름차순 정렬을 해줘야 한다.

 

또한, 사용했던 숫자를 재사용할 수 있기 때문에 숫자의 사용 중 여부를 판단하는 배열 또한 필요하지 않다.

 

그리고 수열이 중복되어서 생성될 수 있는데, 이는 중복을 허용하지 않는 set을 활용해서 처리했다.

 

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, arr[7], num[7];
set<vector<int > > st;
vector<int> v;
void func(int k) {
	if (k == m) {
		for (int i = 0; i < m; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}
	for (int i = 0; i < n; i++) {
		arr[k] = num[i];
		func(k + 1);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + 1);
	func(0); //0번까지 채워져있다
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1799번: 비숍 (C++)  (0) 2019.07.24
백준 15666번: N과 M (12) (C++)  (0) 2019.07.23
백준 6603번: 로또 (C++)  (0) 2019.07.22
백준 5427번: 불 (C++)  (0) 2019.07.22
백준 2573번: 빙산 (C++)  (0) 2019.07.22

https://www.acmicpc.net/problem/6603

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2

www.acmicpc.net

 

n개의 숫자중에 6개를 뽑아서 수열을 만들고, 오름차순 정렬하여 출력해주면 된다.

 

입력으로 들어오는 숫자는 정렬된다는 조건이 없다는 것을 주의해야 한다.

 

 

1. next_permutation 활용 구현

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[50], Sel[50];
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) return 0;
		
		for (int i = 0; i < n; i++)
			cin >> a[i];
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			if (i < 6) Sel[i] = 0;
			else Sel[i] = 1;
		}
		
		do {
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) cout << a[j] << ' ';
			}
			cout << '\n';
		} while (next_permutation(Sel, Sel + n));
		cout << '\n';
	}
	return 0;
}

 

 

2. 백트래킹 활용 구현

 

마찬가지로 사용할 수 있는 수들을 입력 받은 이후에, 수열을 오름차순으로 만들어내기 위해서 정렬을 수행한다.

 

조합이기 때문에 매 재귀마다 0부터 확인하는 것이 아니라 이전 재귀에서 사용했던 숫자의 위치를 파악해서 그 숫자 이후로 사용할 수 있는 숫자를 찾는다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, num[50], arr[7];
bool isused[50];
int st;
void func(int k) {
	//여기서 수열의 길이 k
	if (k == 6) {
		for (int i = 0; i < k; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	if (k == 0) st = 0; //0일때 초기화
	for (int i = st; i < n; i++) { //조합으로 만들기 위해 st부터. 0부터 뽑으면 순열(순서가 다르면 다른 수열)
		if (!isused[i]) {
			isused[i] = true;
			arr[k] = num[i];
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		sort(num, num + n);
		func(0);
		cout << '\n';
	}
}

https://www.acmicpc.net/problem/1182

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

정수들의 개수와 목표로 하는 합을 입력받는다.

 

정수들로 만들 수 있는 길이가 1 이상인 부분 수열들을 구한다. 그리고 그 부분수열들의 합이 처음에 입력받은 S와 같은 부분수열의 개수를 구하면 되는 문제이다.

 

우선 N개의 숫자를 입력받았다고 가정하면, 1개, 2개, 3개 ... N개로 만들 수 있는 부분수열을 모두 구해야 한다.

 

그리고 매 부분수열마다 합을 계산해서 그 합이 s인지 아닌지 판단해주면 되는 문제이다.

 

즉 조합으로 바꿔서 생각할 수 있고, n이 20 이하로 작으니 백트래킹을 해도 무방하다.

 

직접 재귀로 구현할 수도 있지만 next_permutation을 이용해서 구현했다.

 

 

Sel 배열을 우선 만들어 둔다. 가령 6개 중에 4개를 조합으로 뽑는다면,

 

Sel 배열은 0, 0, 0, 0, 1 1 이렇게 두고 if(!Sel[i]) 일 때 수열이 만들어지게 된다.

 

이를 이용해서 1개부터 n개까지 부분수열을 구해주면 되겠다.

 

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, s, a[20], Sum = 0, Sel[20], cnt = 0;
int main(void) {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < 20; i++)
		Sel[i] = 1;
	for (int i = 0; i < n; i++) {
		Sel[i] = 0; //하나씩 0으로 바꿈
		do {
			Sum = 0;
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) Sum += a[j];
				//if (!Sel[j]) cout << a[j] << ' ';
			}
			if (Sum == s) cnt++;
		} while (next_permutation(Sel, Sel + n));
	}
	cout << cnt << '\n';
	return 0;
}

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

퀸은 놓여있는 위치의 행과 열 그리고 대각선 두 방향을 공격할 수 있다.

 

N이 15 정도밖에 되지 않기 때문에 백트래킹을 해도 충분하다.

 

먼저 행당 1개의 퀸이 있는 것은 당연하다.

 

따라서 우리는 특정 열에 퀸을 놓을 수 있는가, 특정 대각선에 퀸을 놓을 수 있는가를 관리해주면 된다.

 

#include<iostream>
using namespace std;
int n;
bool isused[3][40];
int cnt = 0;
void func(int k) {
	//k-1개 까지 다 놓은 상태
	if (k == n + 1) {
		cnt++;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (isused[0][i] || isused[1][k + i] || isused[2][k - i + n - 1])
			continue;
		isused[0][i] = true;
		isused[1][k + i] = true;
		isused[2][k - i + n - 1] = true;
		func(k + 1);
		isused[0][i] = false;
		isused[1][k + i] = false;
		isused[2][k - i + n - 1] = false;
	}
}
int main(void) {
	cin >> n;
	func(1);
	cout << cnt;
	return 0;
}

https://www.acmicpc.net/problem/15664

 

15664번: N과 M (10)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

 

사용할 수 있는 숫자들 중에 중복되는 숫자가 있을 수 있다.

 

숫자는 중복해서 사용하면 안 되고 입력받은 개수만큼만 사용해야 하며

 

만들어낸 수열은 비내림차순이어야 한다.

 

 

#include<iostream>
#include<vector>
#include<unordered_set>
#include<set>
using namespace std;
int N, M, arr[9], n[9];
bool isused[9];
set<vector<int> > st;
vector<int> v;
void func(int k) {
	
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!isused[i] && arr[k - 1] <= n[i]) {
			isused[i] = true;
			arr[k] = n[i];
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> n[i];
	}
	func(1);
	for (set<vector<int> >::iterator it = st.begin(); it != st.end(); it++) {
		for (int i = 0; i < (*it).size(); i++) {
			cout << (*it)[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/15663

 

15663번: N과 M (9)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

 

쉽게 풀려면 쉽게 풀 수 있는 문제이다.

 

문제를 살펴보자. 먼저 같은 숫자가 여러 번 등장할 수 있다는 조건이 있다.

 

즉 1 9 9 이런식으로 숫자의 목록이 있다면, 길이 2의 수열이 19 19 91 99 91 99 이렇게 3p2개 나올 수 있다는 것이다.

 

이제 중복을 제거해줘야 하고, 오름차순으로 정렬을 해줘야 한다.

 

정렬 방법은, 지금까지 그래 왔던 것처럼 미리 사용 가능 숫자들을 정렬해주면 된다.

 

 

또한 중복을 제거할 때는, 여러가지 방법이 물론 있겠지만, 간단하게 중복을 허용하지 않는 set을 사용했다.

 

set에 어떤 data를 삽입할 때, 이미 같은 데이터가 set 내부에 존재하면, 삽입 시도는 무시된다.

 

 

그런데 이번 문제를 풀던 도중 새로운 사실을 알았다.

 

처음에는 string type으로 공백과 함께 set에 담아서 출력을 하려고 했다.

 

따라서 set<string> 이렇게 타입을 잡았는데, set 안에 들어가게 되면 string을 나중에 꺼내서 사용할 때 string의 길이가 1이 된다는 것이다. 즉 string이 내가 평소에 아는 string이 아니게 된다.

 

 

이 문제를 해결하기 위해 set안에 vector을 넣기로 하고 문제를 해결했다. vector는 이상 없이 작동했다.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int n, m, arr[11], num[11];
bool isused[11];
set<vector<int> > ctnr;
void func(int k) {
	if (k == m + 1) {
		vector<int> v;
		for (int i = 1; i <= m; i++) {
			v.push_back(arr[i]);
		}
		ctnr.insert(v);
		v.clear();
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (!isused[i]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);

	func(1);

	/*for (set<string>::iterator i = ctnr.begin(); i != ctnr.end(); i++) {
		for (int j = 0; j < (*i).length(); j++) {
			if (j % 2 == 0) cout << stoi((*i).substr(j, 1));
			else cout << ' ';
		}
		cout << '\n';
	}*/
	for (auto e : ctnr) {
		for (int i = 0; i < e.size(); i++) {
			cout << e[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/15657

 

15657번: N과 M (8)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

www.acmicpc.net

 

사용할 수 있는 수들을 오름차순 정렬한다.

 

이전 자리에서 사용한 숫자보다 다음에 사용할 자리의 숫자가 크거나 같으면 된다.

 

숫자를 중복해서 사용할 수 있으니, 숫자의 사용 여부를 관리하는 배열도 필요하지 않다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int num[9], arr[9];
int n, m;
void func(int k) {
	if (k == m + 1) {
		for (int i = 1; i <= m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (arr[k - 1] > num[i]) continue; //k가 1이면 arr[] = 0 이라서 상관X
		else {
			arr[k] = num[i];
			func(k + 1);
		}
	}
}
int main(void) {
	
	cin >> n >> m;
	//n개 가지고 길이 m
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);
	func(1);
	return 0;
}

https://www.acmicpc.net/problem/15656

 

15656번: N과 M (7)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다.

www.acmicpc.net

 

숫자를 중복해서 뽑을 수 있기 때문에 숫자의 사용 여부를 관리하는 배열이 필요가 없다.

 

num배열에 사용할 수 있는 수들을 입력받고 정렬해준다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[8], arr[8];

void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		arr[k] = num[i]; //k번째 자리로 i번째 숫자 선택
		func(k + 1); //k+1번째 자리 정하기
	}
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1); //수열이 오름차순으로 나오게 하기 위해 오름차순 정렬
	func(1); //1번째 자리를 선택할 차례

	return 0;
}

+ Recent posts