뚝딱뚝딱

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

💡 암호 만들기

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

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

[출력]
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

✅ 문제 풀이

• vector에 C개의 문자를 입력 받은 후, 알파벳 순으로 정렬해준다.
• des함수는 C개의 각 문자를 포함하는 경우와 포함하지 않는 경우로 재귀 호출된다.
• 처음에는 빈 문자열로 시작했다가, C개의 문자를 차례로 방문하면서 붙이거나, 붙이지 않도록 한다.
• 그래서 붙인 문자열이 L개가 되면 res 벡터에 문자열을 넣어두고, des함수를 멈춘다.
• 그렇지 않다면 des함수를 호출해 붙일 문자를 붙여 넘긴 것과, 붙이지 않고 넘긴 것으로 두번 호출한다. 그리고 현재 가리키는 문자를 cnt로 정의하여 +1해준 값을 넘겨준다.
• 그리고 des함수가 종료되고 나면, res에 있는 크기가 L인 문자열들을 걸러내야 한다. 문제에서 주어진 빨간 색 조건에 맞도록 한다.
• 즉 모음이 1개 이상이고, 자음이 2개 이상인지 확인 한다.
• res 벡터를 순회하면서 각 문자열에 모음과 자음을 count한다. 모음이 1개 이상이고 자음이 2개 이상이면 화면에 출력하도록 하고, 그렇지 않으면 출력하지 않는다.

✏ 코드 전문

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int L, C;
vector<string> res;
void des(vector<string> alp, string sum, int cnt) {
	if (sum.length() == L) {
		res.push_back(sum);
		return;
	}
	if (cnt < C) {
		des(alp, sum + alp[cnt], cnt + 1);
		des(alp, sum, cnt + 1);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> L >> C;

	vector<string> alp;
	for (int i = 0; i < C; i++) {
		string ch;
		cin >> ch;
		alp.push_back(ch);
	}

	sort(alp.begin(), alp.end());

	des(alp, "", 0);
	
	
	for (int i = 0; i < res.size(); i++) {
		int moem=0;
		int jaem = 0;
		for (int j = 0; j < res[i].length(); j++) {
			if (res[i][j] == 'a' || res[i][j] == 'e' || res[i][j] == 'i' || res[i][j] == 'o' || res[i][j] == 'u') moem++;
			else jaem++;

			if (moem >= 1 && jaem >= 2) {
				cout << res[i] << "\n";
				break;
			}
		}
	}

	return 0;
}

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

💡 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

[입력]
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

[출력]
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

✅ 문제 풀이

• DFS와 BFS의 로직을 나누어서 두번의 결과를 따로 구하고 출력하도록 하였다.
• 일단 입력으로 받은 간선의 정보를 2차원 벡터에 저장하였다.
  이때 양방향 간선이라는 점을 고려하여, A->B로 B->A로의 간선 정보를 저장해준다.
• S노드에서 시작하므로, S번의 visited를 true로 설정하고 시작한다.
• 간선 정보를 담은 arr배열을, 각 노드에 대해서 오름차순 정렬해준다. 노드 번호가 낮은 것부터 방문해야 하기 때문이다.
• dfs함수는, arr배열의 s번 vector를 탐색하는데, 먼저 방문하는 노드를 시작으로 또 dfs를 재귀호출하며 방문하도록 한다. 
• bfs함수는, arr배열의 s번 vector를 탐색하는데, 각 노드를 탐색할 때마다 queue에 담아주고, 해당 벡터를 다 탐색하고 나서는 queue의 front부터 탐색하며 bfs를 재귀호출하도록 한다.
• 각각의 결과는 dfs_result, bfs_result에 담은 후 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

void dfs(int s, vector<vector<int>> arr, vector<bool> &visited, vector<int> &dfs_result) {
	for (int i = 0; i < arr[s].size(); i++) {
		if (!visited[arr[s][i]]) {
			visited[arr[s][i]] = true;//방문
			dfs_result.push_back(arr[s][i]);
			dfs(arr[s][i], arr, visited, dfs_result);
		}
	}
}
void bfs(int S, vector<vector<int>> arr, vector<bool> &visited, vector<int> &bfs_result, queue<int> &q) {
	for (int i = 0; i < arr[S].size(); i++) {
		if (!visited[arr[S][i]]) {
			visited[arr[S][i]] = true;//방문
			q.push(arr[S][i]);
			bfs_result.push_back(arr[S][i]);
		}
	}
	while (!q.empty()) {
		int next = q.front();
		q.pop();
		bfs(next, arr, visited, bfs_result, q);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, S;
	cin >> N >> M >> S;

	vector<vector<int>> arr(N+1);
	vector<bool> visited1(N + 1, false);//dfs에서사용
	vector<bool> visited2(N + 1, false);//bfs에서사용
	queue<int> q;//bfs에서 사용
	vector<int> dfs_result;
	vector<int> bfs_result;
	for (int i = 0; i < M; i++) {//간선 정보 입력받기
		int n1, n2;
		cin >> n1 >> n2;

		arr[n1].push_back(n2);
		arr[n2].push_back(n1);
	}

	for (int i = 1; i < N + 1; i++) {//노드별로 간선 정보를 오름차순 정렬
		sort(arr[i].begin(), arr[i].end());
	}


	visited1[S] = true;
	visited2[S] = true;
	dfs_result.push_back(S);
	bfs_result.push_back(S);

	dfs(S, arr, visited1, dfs_result);
	bfs(S, arr, visited2, bfs_result, q);

	for (int i = 0; i < dfs_result.size(); i++) {
		cout << dfs_result[i]<<" ";
	}
	cout << "\n";
	for (int i = 0; i < bfs_result.size(); i++) {
		cout << bfs_result[i] << " ";
	}
	
	return 0;
}

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

💡 기타줄

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.
끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

[입력]
첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

[출력]
첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

✅ 문제 풀이

• 일단 세트 가격과 낱개 가격의 최소 값을 각각 저장하는 변수를 지정한다.
• 입력을 받을 때마다 현재의 최소값과 비교하면서, 세트와 낱개의 각각 최소값을 구한다.
• 기타줄 개수인 N을 6으로 나누었을 때 나머지가 존재하면 그 몫보다 1 큰 만큼을 최소 세트값과 곱한 값, N만큼을 낱개로만 샀을 때의 값, N을 6으로 나누었을 때의 몫 만큼을 최소 세트값과 곱한 값+6으로 나눈 나머지에 최소 낱개값과 곱한 값을 더한, 이 세가지 결과 중 가장 작은 경우가 이 문제의 최종 답이 된다.

✏ 코드 전문

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	int smin = 1000;
	int omin = 1000;
	for (int i = 0; i < M; i++) {
		int s, o;
		cin >> s >> o;

		smin = min(smin, s);
		omin = min(omin, o);
	}

	int base = smin * (N / 6);
	int temp = min((N%6==0) ? base : base + smin, base + (N % 6)*omin);
	cout << min(omin * N, temp);

	return 0;
}

• base의 경우 N이 6의 배수로써 딱 떨어질 수 있고, 나머지가 있을 수 있음.
• 따라서 세트로만 살 경우에서는, 만약 N이 6배수이면 base 그대로 계산하고, 나머지가 존재한다면 +1하여 계산하도록 하였음.
• min함수는 인자를 두개만 받으므로, 세개를 비교하기 위해 두개를 먼저 비교하고 그 결과를 cout으로 바로 나머지 하나와 함께 비교하여 출력하도록 하였음.

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

💡 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.예를 들어 S=0001100 일 때,전체를 뒤집으면 1110011이 된다.4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

[입력]
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

[출력]
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

✅ 문제 풀이

• 문자열의 첫 문자를 기준으로 해서 문자열을 앞에서부터 순회한다.
• 첫 문자를 now에 저장해두고, 비교하다가 문자가 다르면 count를 해주고 now에 그 문자로 바꾸어준다.
• 위 과정을 반복하고 나면 최종 count값이 설정된다.
• count값이 홀수이면 0을1로, 1을 0으로 바꾸는 횟수가 똑같기 때문에, count를 2로 나눈 몫에 1을 더한 것과 같다.
• count값이 짝수이면, 0을 1로, 1을 0으로 바꾸는 횟수가 둘 중 하나가 더 적기 때문에, count를 2로 나눈 몫과 같다.

✏ 코드 전문

#include<iostream>
#include<string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str;
	cin >> str;

	int count=0;
	char now = str[0];
	for (int i = 1; i < str.length(); i++) {
		if (now != str[i]) {
			count++;
			now = str[i];
		}
	}

	if (count % 2 == 1) {
		count /= 2;
		count++;
	}
	else {
		count /= 2;
	}

	cout << count;

	return 0;
}

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

💡 방 번호

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.
다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

[입력]
첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

[출력]
첫째 줄에 필요한 세트의 개수를 출력한다.

✅ 문제 풀이

• 주어진 방번호 N의 각 자리 수를 구해야한다.
  N을 10으로 나눈 나머지를 구하면 된다.
• 그리고 그 값을 카운트 해준 후, N을 10으로 나눈 몫으로 갱신한다.
• 카운트 하기 위해서 0부터 9까지의 출현 빈도를 저장할 배열을 선언해준다.
• 만약 각 자리의 수가 6또는 9이면, 6번 인덱스와 9번 인덱스의 값을 비교해서 똑같은 경우 6에 먼저 카운트 되도록 하고, 아니면 9에 카운트 되도록 한다.
  6과 9는 뒤집어서 서로를 사용할 수 있기 때문이다.
• 그렇지 않다면 그냥 그 수에 해당하는 인덱스의 값에 카운트 되도록 한다.
• 필요한 상자수는 배열에서 가장 MAX인 값과 같게 된다.

✏ 코드 전문

#include<iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int arr[10] = { 0 };
	int N;
	cin >> N;

	while (N > 0) {
		if (N % 10 == 6 || N % 10 == 9) {
			if (arr[6] == arr[9]) arr[6]++;
			else arr[9]++;
		}
		else arr[N % 10]++;

		N /= 10;
	}

	int max = arr[0];
	for (int i = 1; i < 10; i++) {
		if (max < arr[i]) max = arr[i];
	}

	cout << max;

	return 0;
}

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

💡 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

[출력]
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

부분수열의 개념을 정확히 몰라서 처음에는 연속적인 수열을 생각했는데, 그냥 수열 내 부분집합이라 생각하면 된다.

단, 공집합은 제외한다.

✅ 문제 풀이

• 처음에는 visited 배열을 선언하고 방문 여부를 바꾸면서 백트래킹으로 해결하려했으나, 코드가 복잡하고 한눈에 안들어와서 매우 간단한 재귀함수 풀이로 바꾸었다.
• func(num, sum)라는 함수를 사용할 건데, num은 현재 수열에서 몇개까지 봤는지이고, sum은 수열에서 num번째 수를 포함하거나 포함하지 않은 값이다. 즉 누적 합이다.
• func()함수 내에서 만약 num이 N이면, 즉 끝까지 다 방문했을경우에, sum이 S와 같으면 answer를 하나 올려준다. 그리고 return을 통해 더이상 재귀가 일어나지 않도록 한다.
• 그리고 다음 값을 더하지 않는 경우 func(num+1, sum)와 다음 값을 더하는 경우 func(num+1, sum+arr[num])로 두번 호출하여 재귀를 이어나가도록 한다.
• 그림으로 나타내면 다음과 같다. 그림에서는 예제의 값으로 사용하였다.

수열의 num번째 값을 더한 쪽을 왼쪽, 안더한 쪽을 오른쪽으로 하여 가지치기 형태로 재귀를 호출하게 된다.

보면 맨 오른쪽의 아무것도 더하지 않는 공집합이 포함되어 있음을 알 수 있다.

• num은 0, sum은 0부터 시작한다. 
• func(0,0)을 하고 나면 count 된 값이 answer가 된다.
• 주의할 점은, S가 0인 경우에, 공집합의 0도 count에 포함시켜버리므로, 이런 경우에는 answer를 하나 빼주면 된다. 

✏ 코드 전문

#include<iostream>

using namespace std;

int N, S, answer=0;
int *arr;

void func(int num, int sum) {
	if (num == N) {
		if (sum == S) {
			answer++;
		}
		return;
	}
	func(num + 1, sum);
	func(num + 1, sum + arr[num]);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;

	arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	
	func(0, 0);

	if (S == 0) answer--;

	cout << answer;

	return 0;
}