뚝딱뚝딱

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/7576

💡 토마토

✅ 문제 풀이

• BFS를 활용하는 문제이다.
• queue를 사용하여 방문해야 할 곳을 pair<int,int> 형태의 좌표를 저장하도록 하였다.
• 먼저 토마토에 대한 2차원 배열을 순회하면서 값이 1이면 그 위치를 q라는 queue에 pair<int,int> 형태로 넣는다.
• 모두 탐색한 후에는 while문으로 q가 빌때까지 bfs를 수행한다.
• q에서 가장 앞에 있는 front의 first와, second를 bfs의 인자로 넘겨준다.

• BFS함수의 동작
  1. 인자로 받은 위치를 가지고, 동 서 남 북 방향에 있는 값이 배열의 인덱스 범위에 유효하며, 값이 0인지 확인한다.
  2. 위의 조건을 만족한다면 해당 위치의 arr값을 1로 변경해주고, temp라는 이름의 queue에 해당 위치를 pair<int,int> 형태로 넣어준다.

• BFS함수를 돌고 나면 q에서 pop한다.
• 그런다음, 현재 q가 비어있다면, 하루에 익을 수 있는 토마토는 다 익은 것이므로 하루를 카운트 하기 위해 answer를 1 증가시킨다.
• 새로 익어진 토마토에 대한 정보를 가진 temp 있는 위치 정보들을 q에 다 옮겨놓는다.
• 그리고나서 이어지는 다음 while문 동작부터는 다음 날짜에 대한 동작을 진행하는 것이다.
• 그런데, q가 비어지게 되면 temp가 비어있고, 그날이 마지막 날이었더라도 하루가 무조건 더해지게 되기 때문에, 마지막에는 answer에서 1을 뺀 값이 답이된다.
• while문을 모두 수행하고 나면, 갱신된 2차원 배열을 순회하면서, 하나라도 0이 있는 값이 있는지 찾아본다.
• 이는 0이 하나라도 있다면 모든 토마토가 익어질 수 없다는 뜻이므로 -1을 출력하고 프로그램을 종료하기 위함이다.
• 그렇지 않다면 answer-1을 출력하도록 하여, 토마토 판에서 토마토가 다 익는데 걸리는 날을 출력한다.

✏ 코드 전문

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

using namespace std;

int n, m;
vector<vector<int>> arr;
queue<pair<int, int>> q;
queue<pair<int, int>> temp;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int answer = 0;

void bfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&arr[nx][ny] == 0) {
			arr[nx][ny] = 1;
			temp.push(pair<int, int>(nx, ny));
		}
	}
}

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

	cin >> m >> n;

	arr.resize(n,vector<int>(m));

	bool end = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push(pair<int,int>(i, j));
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while(!temp.empty()) {
				q.push(pair<int,int>(temp.front().first, temp.front().second));
				temp.pop();
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	cout << answer-1;

	return 0;
}

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

💡 평범한 배낭

[문제]
이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

[입력]
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.입력으로 주어지는 모든 수는 정수이다.

[출력]
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

✅ 문제 풀이

• 배낭 문제는 전형적인 DP 문제
• 배낭 문제 중에는 물건의 무게를 쪼갤 수 있는 fraction knapsack 문제와 쪼갤 수 없는 0-1 knapsack 문제로 구분할 수 있다.
• 이 문제는 0-1 knapsack에 해당한다.
• 1번 물건부터 n번 물건까지 각각의 물건을 넣을지 말지에 따라서 무게k 안에 담을 수 있는 최대 가치는 달라진다.
• 이를 계산하기 위해 2차원 배열을 사용한다.
• dp[i][j]에서 i는 i번째 물건까지 고려하면서 최대로 담을 수 있는 배낭의 무게가 j일때의 최대 가치를 갖는다.
• 따라서 dp[i][j]를 구할 때는 i번 째 물건을 넣지 않은 경우와 넣은 경우 중 더 큰 가치를 반영하도록 한다.
  이는 i번째 물건의 무게가 j 이하여야 넣을 수 있기 때문에, 이를 꼭 확인한다.
  i번째 물건을 넣지 않는다면, i-1번째 물건까지 고려했을 때의 가치와 같다.
  i번째 물건을 넣는다면, i번째 물건의 가치+dp[i-1][j-i번째 물건의 무게]와 같다. (i번째 물건의 무게만큼 빼줘야 i를 넣음으로써 배낭의 무게가 j이하로 유지할 수 있기 때문이다)
  이 두 값 중 더 큰 값이 dp[i][j]가 된다.
• 그런데 만약 i번째 물건의 무게가 j보다 크다면, 배낭에 넣을 수 없기 때문에, 이때의 dp[i][j]는 i-1번째 물건까지 고려했을 때의 가치와 동일하게 된다. 어차피 못넣기 때문이다.
• 그렇다면 다음 두가지 경우에 대해서 각각의 점화식을 나타낼 수 있다.
  
  

🅰 j < i번째 물건의 무게

dp[i][j] = dp[i-1][j]

🅱 j >= i번째 물건의 무게

dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

• 입력으로 받은 물건의 개수 n, 배낭에 담을 수 있는 최대 무게 k
• 2중 for문을 통해 i는 1부터 n까지, j는 1부터 k까지 순회하며 dp[i][j]를 계산할 수 있다.
• 이때 점화식에 의해서, 아직 2중 for문을 통해 계산되지 않은 범위의 dp값을 사용하게 되는 경우가 있는데, 이는 결국 조건을 충족하지 못해 0으로 계산되어야 한다. 따라서 처음에 2차원 배열 dp를 생성할 때, 크기가 (n+1) * (k+1)인 배열로 선언하고, 값은 모두 0으로 초기화 하여 시작하였다. 이렇게 하면 0 값을 가져다 쓸 수 있다. 
• 2중 for문으로 dp를 모두 계산하고 나면, dp[n][k]에는 n번 물건까지 고려하여 배낭에 담을 수 있는 최대 무게가 k일때의 최대 가치가 담기게 된다.
• 따라서 dp[n][k]를 출력해준다. 

✏ 코드 전문

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

using namespace std;

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

	int n, k;
	cin >> n >> k;

	vector<int> w(n+1,0);
	vector<int> v(n+1,0);
	
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}

	vector<vector<int>> dp(n + 1, vector<int>(k + 1,0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < w[i]) {
				dp[i][j] = dp[i-1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
			}
		}
	}

	cout << dp[n][k];

	return 0;
}

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

💡 분할과 정복 ** 쿼드트리 문제와 유사

[문제]
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

[입력]
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

[출력]
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

✅ 문제 풀이

• 분할과 정복을 통해 해결할 수 있는 문제이다.
• 문제는 처음 size에서 3등분 해가며 분할한다.
• 입력으로 주어진 size에서 시작하여, size 만큼 배열을 순회한다.
• 순회하다가 첫 값과 달라지는 부분이 발생하면, 9등분으로 나뉘어야 하기 때문에, size를 3등분 한다.
• 그리고 해당 함수를 각 9등분의 첫 값의 좌표에 맞추어 9번의 재귀호출을 한다.
• 첫번째 조각의 첫 좌표는 이전의 첫 좌표와 항상 동일하고, 두번째 조각의 첫 좌표는 y를 size만큼 더한 값이고, 세번째 조각의 첫좌표는 y를 size*2만큼 더한 값이다.
• 네번째 조각의 첫좌표는 x를 size 만큼 더한 값이고, 다섯번째 조각의 첫좌표는 x와 y 모두 size 만큼 더한 값이다...
• 이렇게 9등분을 차례차례 좌표를 부여하고 재귀호출 하면된다.
• 재귀호출 뒤에는 동작이 없기 때문에 바로 return하도록 하고, 만약 해당 size에서 모든 값이 동일했다면, 해당 값을 1 count하도록 한다.
• 이때 카운트는 map을 통해서 -1, 0,1을 key로 하였고, 0으로 자동 초기화 되는 값에 증가 연산자로써 연산되도록 구현하였다.  

✏ 코드 전문

#include<iostream>
#include<vector>
#include<map>

using namespace std;

int n;
vector<vector<int>> arr;
map<int, int> m;

void func(int size, int x, int y) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arr[x][y] != arr[i][j]) {
				int new_size = size / 3;
				func(new_size, x, y);
				func(new_size, x, y + new_size);
				func(new_size, x, y + new_size * 2);
				func(new_size, x + new_size, y);
				func(new_size, x + new_size, y + new_size);
				func(new_size, x + new_size, y + new_size * 2);
				func(new_size, x + new_size * 2, y);
				func(new_size, x + new_size * 2, y + new_size);
				func(new_size, x + new_size * 2, y + new_size * 2);
				return;
			}
		}
	}
	m[arr[x][y]]++; //해당 키가 map에 없으면, 자동으로 키 생성 및 0으로 초기화하고 증가시킴.
}

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

	cin >> n;

	arr.resize(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	func(n, 0, 0);

	cout << m[-1] << "\n" << m[0] << "\n" << m[1];

	return 0;
}

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

💡 RGB거리

[문제]
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

[입력]
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

✅ 문제 풀이

이 문제는 전형적인 DP 문제이다.

집은 R,G,B 세 색상 중 하나로 칠할 수 있는데, 인접한 집끼리는 색이 겹쳐서는 안된다.

그렇게 칠했을 때 모든 집을 칭하는 최소 비용을 구한다.

일단 입력으로 주어지는 각 집당 페인트 비용을 저장하기 위해서 2차원 배열을 사용해보자.

문제에서 주어진 예시를 사용할 것이다.

행은 집의 번호, 열은 각 집의 R,G,B 비용이다.

첫번째 집까지 칠했을 때는 첫번째 집에서 고른 비용이 저장되는 것이고, 두번째 집까지 칠했을 때는 첫번째 집까지 쓰인 비용+두번째 집에서 고른 비용으로 값이 정해진다. 따라서 다음과 같은 점화식을 따른다.

d[i]=d[i-1]+a[i]

그런데, 비용을 최소로 한다고 해서 모든 집에서 가장 작은 비용을 선택해버린다면, 위 예에 따르면 26, 49, 13이 가장 최소가 되어버리고, 모두 빨간색으로만 칠하게 되어버린다. 이는 조건을 위배하게 된다.

따라서 이전 집에서 어떤 색을 칠했는지에 따라서 이번 집에 칠할 수 있는 색이 2개로 추려져야 한다.

그러므로 이전 집을 R로 칠했을때, G로 칠했을때, B로 칠했을때를 모두 계산하고 나서, 최종 집까지 칠했을때 세 값중 최소값이 답이 될 수 있다.

이때 현재 집(i번 집)에 R을 칠하고자 한다면 이전집(i-1)이 G또는 B가 칠해졌어야 하고, 이 둘 중 최소 비용에 현재 집의 R 비용을 더한 값이 d[i][0]이 될 수 있다.

이를 점화식으로 나타내면 다음과 같다.

d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]; 
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];

점화식에 따르면 위 표와 같이 정리될 수 있고, 이는 i번째 집까지 칠했을 때의 비용을 나타낸다.

따라서 위 예시의 답은 3번째 집까지 칠했을 때의 비용 96,172,146 중에 최소값인 96이 되는 것이다.

min(min(d[t][0], d[t][1]), d[t][2])

이 식을 통해서 답을 구할 수 있다. (t는 마지막 집의 번호이다)

✏ 코드 전문

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

using namespace std;

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

	int t;
	cin >> t;

	vector<vector<int>> d(t + 1, vector<int>(3, 0));
	vector<vector<int>> a(t + 1, vector<int>(3, 0));

	for (int i = 1; i <= t; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
	}

	int answer = min(min(d[t][0], d[t][1]), d[t][2]);

	cout << answer;

	return 0;
}