뚝딱뚝딱

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

💡 별 찍기 -10

✅ 문제 풀이

• 프렉탈 도형 문제
• 재귀함수를 사용한 분할과 정복으로 해결할 수 있다
• 도형의 패턴을 분석해보자.

위는 N=3일때의 도형의 출력 형태이다. 좌표로 따졌을 때 (1,1)만 비어있음을 알 수 있다.

위는 N=9일때의 도형의 출력 형태이다. 좌표로 따졌을 때 (1,1),(1,4),(1,7),(3,3),(3,4),(3,5),(4,1),(4,3),(4,4),(4,5),(4,7),(5,3),(5,4),(5,5),(7,1),(7,4),(7,7)이 비어있음을 알 수 있다.

좌표를 보니,  (i/3)%3==1 과 (j/3)%3==1을 만족하는 경우에 비어있음을 확인할 수 있다.

또한 3*3 개별 도형들의 빈 자리는 (i/1)%3==1 과 (j/1)%3==1을 만족하는 경우에 비어있음을 확인할 수 있다.

따라서 중간에 나누어 지는 값은 3*3 도형이 한 변에 만들어지는 개수로 생각할 수 있고, 이는 n을 3으로 나누어가며 위의 공식에 만족할 경우 " "를, 그렇지 않으면 *을 출력하도록 하면 된다.

즉, *이 출력되는 경우는 위의 공식을 만족하지 않는 위치일 경우, 별을 하나 출력한다고 생각하면 되고, 그때마다 3*3 하나를 기준으로 하므로 num은 1이 될 것이다.

✏ 코드 전문

#include<iostream>

using namespace std;

void star(int i, int j, int num) {
	if ((i / num) % 3 == 1 && (j / num) % 3 == 1) {
		cout << " ";
	}
	else {
		if (num / 3 == 0) {
			cout << "*";
		}
		else {
			star(i, j, num / 3);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			star(i, j, n);
		}
		cout << "\n";
	}

	return 0;
}

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

💡 하노이 탑 이동 순서

✅ 문제 풀이

• 하노이 탑 문제는 재귀호출을 통해 풀이 할 수 있다.
• 하노이 탑의 다음과 같은 공식 때문이다.
• 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다. 탑 3에 있는 가장 작은 원판을 탑 2로 옮긴다. 탑 2에 있는 가장 작은 원판을 탑 1로 옮긴다. 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다.
• k-1개의 원판은 위 공식을 따르게 된다. 
• 따라서 각 원판을 재귀 호출을 통해 이동 순서를 표현할 수 있다.
• 정리하자면, 1->3->2, 2->1->3 순서로 이동하게 된다.
• 이를 위해 hanoi라는 함수를 선언해준다.
• 이 함수는 현재 원판의 번호(=크기)와 시작(from), 중간(by), 끝(to) 지점을 인자로 갖는다.
  만약 원판의 번호가 1이면 "from to"을 출력하도록 한다.
  그렇지 않다면 hanoi를 호출하고 인자로 원판의 번호-1, from, to, by 순서로 넣어준다. 이는 1->3->2 순서를 나타낸 것이다.
  그리고 이 함수를 호출한 후에는 "from to"를 호출하여 이동 상황을 출력한다.
  그다음, hanoi를 한번 더 호출하여 인자로 원판의 번호-1, by, from, to 순서로 넣어준다. 이는 2->1->3 순서를 나타낸 것이다.
• 따라서 원판 하나에 대해 hanoi 함수는 두번 재귀호출 하므로, 연산이 2^k번 발생하는데, 가장 큰 원판은 바로 이동할 수 있으므로 1을 빼준다. 따라서 총 이동 횟수는 2^k-1이 된다.
• 참고로 c++의 경우, pow함수를 사용할 때 int로 형변환을 해주지 않으면 결과가 틀렸습니다가 나오므로, int로 꼭 변환한 후 -1을 빼주도록 한다. (pow함수의 반환 형태는 double 형이기 때문) 

✏ 코드 전문

#include<iostream>
#include<math.h>

using namespace std;

void hanoi(int n, int from, int by, int to) {
	if (n == 1) {
		cout << from << " " << to << "\n";
	}
	else {
		hanoi(n - 1, from, to, by);
		cout << from << " " << to << "\n";
		hanoi(n - 1, by, from, to);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int k;
	cin >> k;

	cout << int(pow(2, k)) - 1 << "\n";
	hanoi(k, 1, 2, 3);

	return 0;
}

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;
}