뚝딱뚝딱

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

💡 동전 1

✅ 문제 풀이

• 배낭 문제와 접근 방식이 동일하다.
• dp를 이용해 경우의 수를 구해나간다.
• dp[i]=j 는 "n가지 종류의 동전을 이용해서 합이 i원이 되도록 하는 경우의 수가 j개" 라는 뜻이다.
• dp[0]=1이다. 합이 0원이 되는 경우의 수는 아무것도 합하지 않는 경우 1개가 존재하기 때문이다. 따라서 이는 초기값이 된다.
• 만약 동전 종류 중 1원짜리가 있다고 하자. 1원을 가지고 1원을 만드는 경우의 수는 다음과 같다.
  dp[1]=dp[1]+dp[0]
  1원이 되려면, 0원에다가 1원을 더해주면 되니까 0원이 되는 경우의 수를 합해주면 된다. 따라서 1이다.
• 만약 동전 종류 중 3원짜리가 있다고 하자. 3원을 가지고 5원을 만드는 경우의 수는 다음과 같다.
  dp[5]=dp[5]+dp[2]
  5원이 되려면, 2원에다가 3원을 더해주면 되니까 2원이 되는 경우의 수를 합해주면 된다. 
• 즉 dp[i]를 구하려면 i에서 동전 가치 "value[j]"를 빼준 값이 되는 경우에다가 그냥 value[j]를 더하면 i원이 되는 거니까. dp[i-value[j]]를 구하는 것과 동일하다. 즉 i-value[j]원이 되는 경우의 수를 구하는 것과 같다.
• 주의할 점은 어떤 value[j]를 가지고서 i원이 되도록 할 때, i는 value[j]보다 커야 한다는 것이다.
  예를 들어, 3원을 더함으로써 4원을 만들어낼 수 있지만, 3원을 더함으로써 2원을 만들어낼 수는 없다. 이미 3이라는 가치가 2보다 크기때문에, 3원을 더하려면 항상 3원 이상의 큰 가치만을 만들어 낼 수 있다.
• 따라서 다음과 같은 점화식을 따른다.
  dp[i]+=dp[i-value[j]]
  (이때, i>=value[j])
• 위를 모든 동전의 종류에 대해서 반복해주면 된다.
• 최종 답은 dp[k]이다. k원을 만드는 경우의 수 이기 때문이다.   

✏ 코드 전문

#include<iostream>
#include<vector>

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> value(n);
	for (int i = 0; i < n; i++) {
		cin >> value[i];
	}

	vector<long long> dp(k + 1,0); //출력 범위가 2^31 까지 임에 주의하여 long long으로 선언

	dp[0] = 1;//0원을 만드는 데 필요한 경우의 수 1

	for (int i = 0; i < n; i++) {
		for (int j = value[i]; j <= k; j++) {
			dp[j] += dp[j - value[i]];//j원을 만드는데, value[i]원을 사용하려면 j에서 value[i]를 뺀 값이 필요하고, 이것의 경우의 수를 더해주면 됨.
		}
	}

	cout << dp[k];

	return 0;
}

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

💡 Fly me to the Alpha Centauri

✅ 문제 풀이

• 시작지점 x와 끝지점 y의 사이 거리를 구하고, 그 거리는 최소 몇번의 이동이 필요한지 구한다.
• 무조건 처음시작과 마지막 이동은 1씩 이동한다. 따라서 y-x에서 2(처음, 끝)를 뺀 거리만을 가지고 몇번 이동할 수 있는지 구하면 된다.
• 만약 y-x-2의 결과가 0 이하라면, 즉 y-x가 1 또는 2 였다면, 시작과 끝을 제외하고는 중간에서 이동하는 거리가 없기 때문에 1이면 1번 이동하는것이고, 2이면 2번 이동하는 것이된다.
• 다음과 같은 수학적 규칙에 따라 거리마다의 최소 이동 횟수를 구할 수 있다.

• 시작과 끝의 각각 1만큼의 이동 거리를 빼고 생각해보자.
• dis = y-x-2 일때, dis가 1일때부터 이동 횟수를 구해보자. 이때 처음이 1이고, 마지막도 1이었기 때문에, 시작도 마지막도 (0,1,2)에서 고를 수 있게 되어야 한다.
• 1 : 1 => 1
  2 : 2 => 1
  3 : 1,2 => 2
  4 : 2,2 => 2
  5 : 1,2,2 => 3
  6 : 2,2,2 => 3
  7 : 2,3,2 => 3
  8 : 2,2,2,2 => 4
  9 : 2,3,2,2 => 4
  10 : 2,3,3,2 => 4
  11 : 2,3,3,2,1 => 5
  12 : 2,3,3,2,2 => 5
  13 : 2,3,3,3,2 => 5
  14: 2,3,4,3,2 => 5
  15 : 2,3,4,3,2,1 =>6
  16 : 2,3,4,3,2,2 => 6
  17 : 2,3,4,3,3,2 => 6
  18 : 2,3,4,4,3,2 => 6
  ...
  보면, 규칙이 있는걸 확인할 수 있다.
  이동횟수가 1인게 2개, 2인게 2개, 3인게 3개, 4인게 3개.... 
  두 묶음씩 동일한 이동횟수를 갖는 dis의 개수가 하나씩 늘어나고 있다.
  (이동 횟수) => dis의 개수 로 따지면
  (1,2) => 2+2
  (3,4) => 3+3
  ...
  dis의 개수가 같은 것끼리 묶어보면, 4, 6, 8, 10 ...이렇게 늘어나는 것을 알 수 있다.
  이를 누적하면 4, 10, 18, 28....인데, 이 수열을 수식으로 나타내보면 다음과 같다.
  a1 = 4
  a2 = a1+(a1+2)
  a3 = a1+(a1+2)+(a1+2+2)
  a4 = a1+(a1+2)+(a1+2+2)+(a1+2+2+2)
  ...
  an = n*a1+n(n-1) = n*n+3n 으로 정리할 수 있다.
• 이제 dis와 n^2+3n 을 가지고, n=1부터 계산하여 n^2+3n이 dis보다 작으면 n을 늘리고 dis보다 커지면 해당 n을 통해 이동 횟수를 구할 수 있다. 이는 while 문으로 n을 결정할 수 있다
•  이동횟수가 {1,2}인것부터 n=1이고, 그 뒤로 한 묶음씩 n을 늘려가면 된다.
• 예를 들어 dis가 15이면 n=3임을 구할 수 있는데, n*2를 한 6과 n*2-1를 한 5 둘 중 하나가 15의 최소 이동횟수 후보가 된다.
• 근데 n^2+3n-n인 n^2+2n보다 dis가 작으면 n*2-1에 해당하는 5가 답이 되는것이고, 그렇지 않으면 n*2에 해당하는 6이 답이 되는 것이다.

• 따라서 이러한 수학적 규칙과 식을 이용하여 이동 횟수를 쉽게 구할 수 있다.
• 이 문제에서 주의할 점은, 입력으로 주어지는 x와 y의 범위가 2^31까지 이기 때문에, int로 받아 계산하면 안되고, long long으로 받아 계산하여야 한다는 점이다.  

✏ 코드 전문

#include<iostream>

using namespace std;

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

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		long long s, e;//입력단위가 2^31이기 때문에 long long으로 받아야 data손실이 없음!!!
		cin >> s >> e;

		long long n = 1;
		long long dis = e - s - 2;

		if (dis <= 0) {
			cout << dis + 2 << "\n";
			continue;
		}

		while ((n*n + 3 * n) < dis) {
			n++;
		}

		if ((n*n + 2 * n) <= dis) n *= 2;
		else n = n * 2 - 1;

		cout << n + 2 << "\n";
	}

	return 0;
}

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

💡 치킨 배달

✅ 문제 풀이

• 이 문제는 완전탐색을 이용해 조합을 만들어내는 것이 관건이다.
• STL을 사용할 수 도 있지만, 직접 조합을 구해내는 알고리즘이 있다.
• 완전탐색을 이용하면 조합을 구할 수 있다. 
• 만약 치킨 집 총 5개 중에서 3곳만 살려두려고 할 때, 그 세곳으로 정할 수 있는 경우의 수를 구해보자.
• 각 치킨 집을 1-5로 번호를 부여하면, {1,2,3},{1,2,4},{1,2,5}....{3,4,5}로 구할 수 있다.
• 이때 주의할 점은 조합의 경우 순열과 달리 순서를 고려하지 않기때문에 {1,2,3}={2,1,3}이다. 따라서 시작이 2였으면, 1은 고려하지 않기로 한다. 1의 경우는 1이 시작이었을 때 이미 다 선택되었기 때문이다.
• 조합을 구하는 알고리즘에 대한 자세한 설명은 페이지를 참고한다.

• 따라서 나는 다음 순서로 이 문제를 해결하였다.
• 치킨집의 위치를 저장하는 벡터 (chichen)을 생성하여 각 치킨 집의 위치를 저장해주었다. 그리고 벡터의 인덱스를 치킨집 번호로 고려하였다.
• 각 집의 위치를 저장하는 벡터 (home)을 생성하여 각 집의 위치를 저장해주었다. 그리고 벡터의 인덱스를 집의 번호로 고려하였다.
• 치킨집의 조합을 저장하는 벡터 (comb)를 생성하여 조합 결과를 저장해주었다. 이때 치킨집의 인덱스를 번호로 하였다.
• 조합을 구할 때 각 치킨 집의 선택 여부를 고려하기 위한 벡터(visited)를 선언하였다.
• 배열을 입력 받을 때, 값이 1이면 집의 위치를 저장하고, 값이 2이면 치킨집의 위치를 저장하도록 하였다.
• 그리고 입력받은 m개의 치킨집으로만 이루어진 조합을 구하기 위해 DFS함수를 선언하고 호출하였다.

• DFS함수는 조합을 생성한다.
• 각 조합에서 시작 인덱스인 s와 현재 몇개까지 담았는지를 나타내는 cnt를 인자로 갖는다.
• 함수 내에서는 cnt가 m이면, visited의 크기만큼 순회해서 값이 true인 인덱스 = 선택받은 치킨집 을 c라는 임시 vector에 저장하고, m개의 선택된 조합이 담긴 c를 comb에 저장하여 하나의 조합에 대해 저장하도록 했다. 그리고 이 경우에는 수행 후 바로 return하여 함수의 재귀호출을 멈춘다.
• 위에 해당하지 않는다면 인자로 주어진 s 인덱스부터 시작하여 나머지 치킨집을 탐색한다. 이때 현재 치킨집의 visited가 true이면 건너뛰고, 그렇지 않으면 true로 해준뒤, DFS를 재귀호출하고, s는 동일하게, 하지만 방금 현재 인덱스를 선택했으므로 cnt+1을 하여 인자로 넘겨준다. 이를 호출하고 난 뒤에는, 또 선택되어져야 하기 때문에, false로 바꾸어준다.
• 이런식으로 재귀호출을 하다가 cnt가 m이 되는 순간에 조합의 결과를 저장하는 것이다.

• DFS함수를 호출할 때 시작 인덱스는 0, 그리고 현재까지 선택된 치킨집 개수도 0이므로, DFS(0,0)을 호출한다.
• 그런다음, comb에 조합이 다 만들어졌기 때문에, 이제 계산만 하면 된다.
• 모든 집은 각 조합 내에 있는 치킨 집과의 거리 중 최소 거리를 구한다.
• 해당 조합에서 모든 집과 치킨 집과의 누적 거리를 구한다.
• 각 조합 간의 누적 거리들 중 최소 값을 구한다.
• 그 값이 최소 거리가 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits.h>//c++17에서는 INT_MAX 정의를 여기서 가져와야해서 필요

using namespace std;
//1. 치킨집의 위치를 갖는 벡터(chicken)를 선언하고 저장해준다. 치킨집의 번호는 인덱스로 구분한다
//2. 일반집의 위치를 갖는 벡터(home)를 선언하고 저장해준다.
//3. 치킨집의 조합을 구한다. 완전탐색으로. 이때 치킨집 번호로 0~chichen.size-1. 조합 결과를 벡터(comb)에 저장한다.

int n, m;
vector<bool> visited;
vector<vector<int>> comb;

void DFS(int s, int cnt) {
	if (cnt == m) {
		vector<int> c;
		for (int i = 0; i < visited.size(); i++) {
			if (visited[i] == true) {
				c.push_back(i);
			}
		}
		comb.push_back(c);
		return;
	}

	for (int i = s; i < visited.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		DFS(i, cnt + 1);
		visited[i] = false;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	int temp;
	vector<pair<int, int>> chichen;
	vector<pair<int, int>> home;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			if (temp == 1) {
				home.push_back(pair<int, int>(i, j));
			}
			else if (temp == 2) {
				chichen.push_back(pair<int, int>(i, j));
			}
		}
	}

	visited.resize(chichen.size());

	DFS(0, 0);

	int answer = INT_MAX;//조합에서 가장 최소로 나올 수 있는 값
	for (int i = 0; i < comb.size(); i++) {
		int dis = 0;//각 조합에서의 최소 거리
		for (int j = 0; j < home.size(); j++) {
			int m = INT_MAX;//내집-치킨집 최소 거리
			for (int k = 0; k < comb[i].size(); k++) {
				int index = comb[i][k];//치킨 집 번호
				m = min(m, abs(home[j].first - chichen[index].first) + abs(home[j].second - chichen[index].second));//내 집에서 이 치킨집까지 거리
			}
			dis += m;
		}
		answer = min(answer, dis);
	}

	cout << answer;
	return 0;

}

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

💡 LCS

✅ 문제 풀이

• 문자열에서 최장 부분 수열의 크기를 찾는 문제
• DP를 이용하여 풀 수 있다.
• dp 배열의 크기는 두 문자열 각각의 크기에 +1 한 만큼으로 행과 열 크기를 배정해준다.
• 행 열 인덱스 0은 모두 0으로 초기화하여 사용할 것이다.
• 그리고 dp 크기만큼 2중 for문을 순회하는데, 각 칸의 값은 해당 칸의 행과 열 알파벳이 동일하면 왼쪽 대각선 위 값에 +1 한 값이고, 다르면 왼쪽과 위에서 오는 값 중 더 큰 값으로 가지게 된다.
  => 이는 표를 그려보면 규칙을 통해 발견할 수 있다.
• 따라서 이를 점화식으로 나타내면 다음과 같다.
  dp[i + 1][j + 1] = dp[i][j] + 1 (행 알파벳=열 알파벳)
  dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) (행 알파벳 =/= 열 알파벳)
  
  
• 그리고 dp[r][c] 즉, 가장 오른쪽 아래에 있는 값이 최종 답이 된다.

✏ 코드 전문

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

using namespace std;

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

	string str1, str2;

	cin >> str1 >> str2;

	int r = str1.length();
	int c = str2.length();

	vector<vector<int>> dp(r+1, vector<int>(c+1,0));
	
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int m = max(dp[i][j + 1], dp[i + 1][j]);
			if (str1[i] == str2[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = m;
			}
		}
	}

	cout << dp[r][c];
	
	return 0;
}

💡 3차원 벡터 정의

vector<vector<vector<int>>> arr

💡 3차원 벡터 resize() 함수 사용

//n,m,h

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

💡 쌍 pair

queue<pair<pair<int,int>, int>> q;

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

토마토 2차원 배열 입력 문제 풀이 참고

2024.01.22 - [CO-TE/백준] - [백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색

💡 토마토(3차원 배열 입력 ver.)

✅ 문제 풀이

• 이전에 풀었던 토마토 (7576번) 문제와 풀이 방식은 동일한데, 입력으로 주어지는 차원이 3차원으로 늘어나 높이까지 고려해야 한다.
• 따라서 입력을 받는 arr 벡터도 3차원으로 정의해주었고, 좌표를 담는 queue의 자료형도 pair를 한번 더 감싸서 3개의 int 쌍을 갖도록 하였다.
  => pair<pair<int,int>,int>
• 입력으로는 한 판 씩 맨 아래 층 부터 들어오기 때문에 for문의 시작에 for문을 하나 더 추가해서 높이마다 한판 씩 정보를 입력 받도록 하였다.
  = 마지막에 확인할 때도 맨앞에 높이에 대한 for문만 추가해주었다.
•  queue에 push할때도 queue의 자료형에 맞게 두 개의 pair 쌍으로 값을 입력해주었다. 여기서 x 와 y 는 전체 pair에서도 첫번째인 pair 쌍에 해당하기 때문에 front().first.first, front().first.second 로 두번씩 들어가 접근하도록 하였고, z는 전체 pair에서 두번째 값이기 때문에 front().second로 접근하도록 하였다.
• 높이에 대한 조건이 추가되면서, 인접한 범위가 위, 아래 까지 늘어났다. 따라서 총 6번의 탐색을 해야하므로, bfs 함수내에서 사용하는 dx, dy를 수정해주었다. 맨뒤에 높이에 대한 변화가 없도록 {0,0}을 추가해준다. 그리고 높이에 대한 dz를 추가해주고, {0,0,0,0,-1,1} 으로 높이에 대해서만 변화가 있도록 한다.
• bfs 함수 내에서 탐색은 4->6으로 수정해주고, 함수의 인자로는 x,y 뿐만 아니라, z도 받도록 하여, 전체 위치를 표시해준다.
• arr의 인덱스 범위에서도 z는 0이상 h이하에 있도록 검사한다.
• 나머지 로직은 동일하다.

✏ 코드 전문

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

using namespace std;

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

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

int answer = 0;

void bfs(int x, int y, int z) {
	for (int i = 0; i < 6; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		int nz = z + dz[i];

		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&& nz>=0 && nz< h&& arr[nx][ny][nz] == 0) {
			arr[nx][ny][nz] = 1;
			temp.push(pair<pair<int, int>, int> (pair<int, int>(nx, ny),nz));
		}
	}
}

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

	cin >> m >> n >> h;

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

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

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

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

	cout << answer - 1;

	return 0;
}