[6주차] 백준 BoJ c++ 풀이 (15664, 17271, 11049, 2533)

들어가기에 앞서

이번 주는 세 문제는 되게 빨리 풀었는데, 마지막 한 문제를 한참동안 걸려서 겨우 풀었다. 그리고 이번 주 문제의 특징은 전부 DP 문제였다. 그래서 아 골드 급에 DP 문제가 많나? 하는 생각이 들정도로 전부 DP 문제였다. 이러다가 DP 마스터가 될 수도 있을 것 같다는 생각을 잠깐 했다...

15664

N과 M 시리즈 문제 중에 하나이다.

저번주에 풀었던 문제와 차이점이 있다면 같은 수를 또 선택할 수는 없다.
그래서 visit 배열을 두고 내가 이 수를 선택했는지 선택하지 않았는지 체킹을 하는 부분만 추가되고, 나머지 부분은 저번주와 동일하다.

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int N, M;
int nums[8];
bool visit[8] = { false, };
vector<int> per;
set<vector<int>> answer;

void dfs(int prev, int depth) {
	if (depth == M) {
		if (answer.find(per) == answer.end()) {
			answer.insert(per);
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			if (!visit[i] && nums[i] >= prev) {
				visit[i] = true;
				per.push_back(nums[i]);
				dfs(nums[i], depth + 1);
				visit[i] = false;
				per.pop_back();
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> nums[i];
	}

	dfs(0, 0);

	for (auto iter = answer.begin(); iter != answer.end(); ++iter) {
		for (int i = 0; i < (*iter).size(); i++) {
			cout << (*iter)[i] << " ";
		}
		cout << '\n';
	}
}

17271

나는 먼저, 크게 세 가지 경우로 나누어 생각했다.

1) N < M 인경우: B스킬의 시간이 전체 초보다 크기 때문에 아예 사용할 수 없다. 따라서 A스킬로 N초를 이루는 하나의 경우만 나타난다.

2) N = M 인 경우: A스킬로 N초를 이루거나 B스킬을 한번 사용하는 경우가 있을 수 있다. 따라서 두 개의 경우의 수만 존재한다.

3) 마지막은 일반적인 경우로 N > M 인 경우: DP를 이용해서 풀 수 있다.

• 1초부터 M-1초까지는 B스킬을 사용하지 못하기 때문에 전부 1개의 경우의 수만 존재한다. 따라서 DP[1] ~ DP[M-1] 까지는 모두 1의 값을 갖는다.
• M초는 A스킬로만 이루어지거나 B스킬 하나로 이루어지는 2개의 경우의 수만 존재한다. 따라서 DP[M] = 2 의 값을 갖는다.
• M+1 <= i <= N일 때 i초부터는 다음과 같다. i초에서 만들 수 있는 경우의 수는 i-1초에서 만들 수 있는 경우의 수에 각각 A 스킬을 하나 추가하는 경우가 있을 수 있다. 즉 dp[i-1] 개의 경우의 수를 갖는다. 또 i-M초에서 만들 수 있는 경우의 수에 B스킬을 하나 추가할 수 있다. 따라서 dp[i-M] 개의 경우의 수도 갖는다. 따라서 최종적으로 dp[i] = dp[i-1] + dp[i-M] 점화식을 도출할 수 있다.

해당 점화식을 사용하여 N초까지 채운다면 최종적으로 dp[N]의 값이 답이 된다.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int N, M;
int dp[10000];

int main() {
	cin >> N >> M;

	if (N < M) {
		cout << 1 << '\n';
	}
	else if (N == M) {
		cout << 2 << '\n';
	}
	else {
		for (int i = 0; i < M - 1; i++) {
			dp[i] = 1;
		}
		dp[M - 1] = 2;
		for (int i = M; i < N; i++) {
			dp[i] = (dp[i - 1] + dp[i - M]) % 1000000007;
		}

		cout << dp[N - 1]<< '\n';
	}
}

11049

이 문제는 저번주에 풀었던 파일합치기 11066번 문제와 동일한 유형의 문제이다.

파일 합치기에서는 dp 배열에 파일을 합치는 비용을 가지고 있고, 두 파일을 합칠 때 두 개의 파일 각각 만들어지는데 필요한 비용과 두 개 파일 크기의 합을 이용했다.

여기에서는 dp 배열에 행렬을 만드는데 필요한 연산 횟수를 가지고 있고, 두 행렬을 합칠 때, 두 개의 행렬 각각 만들어지는데 필요한 연산 횟수와 두 행렬의 사이즈만 알고 있으면 구할 수 있다.

점화식은 위의 그림과 같은데, 이것을 이해하기 힘들다면 파일 합치기의 설명을 참고하는 것이 더 좋다. 이때도 얘기하였지만 점화식을 이해하기 보다는 실제로 하나의 셀이 어떤 연산을 통해 값이 정해지는지를 아는 것이 더 중요하다고 생각한다.

파일합치기 풀이 보러가기, 11066

dp[i][j] = 행렬 i~j까지 다 곱해서 하나의 행렬을 만드는데 필요한 비용을 가지고 있다.

따라서 i = j의 경우에는 나 자신을 만드는데 필요한 연산횟수인데, 이것은 0이기 때문에 dp 배열에서 대각선은 전부 0이 된다.

다음으로 두 행렬의 곱했을 때 최종적인 사이즈를 알아야하는데, 이것은 다음과 같이 알 수 있다.

일단 힌트는
M1 = M X N, M2 = N X L 일 때, 두 개의 행렬을 곱하는데 필요한 연산 횟수는
M X N X L이다. 즉, 이것은 M1의 행 수 X M1의 열 수 X M2의 열수만 알 수 있다면 쉽게 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int N;
pair<int, int> matrix_size[500];
int dp[500][500];

int main() {
	cin >> N;
	int x, y;
	
	fill(&dp[0][0], &dp[500 - 1][500], INT_MAX);

	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		matrix_size[i] = make_pair(x, y);
		dp[i][i] = 0;
	}

	for (int i = N - 2; i >= 0; i--) {
		for (int j = i; j < N - 1; j++) {
			for (int k = j + 1; k < N; k++) {
				pair<int, int> size1 = make_pair(matrix_size[i].first, matrix_size[j].second);
				pair<int, int> size2 = make_pair(matrix_size[j + 1].first, matrix_size[k].second);
				dp[i][k] = min(dp[i][k], dp[i][j] + dp[j+1][k] + (size1.first * size1.second * size2.second));
			}
		}
	}

	cout << dp[0][N - 1] << '\n';
}

2533

사실 2533은 다른 사람의 풀이를 많이 빌렸다. 따라서 정리가 조금 모자랄 수 있다.

일단 아이디어는 트리를 DP로 계산하는 점이고, 가장 밑인 리프노드에서부터 하나씩 채워나가게 된다.

dp[node][0] = node를 root로 하는 서브 트리에서 node가 일반인일 때, 필요한 얼리어답터 수이고, 단말 노드의 경우 0이다.
dp[node][1] = node를 root로 하는 서브 트리에서 node가 얼리어답터일 때, 필요한 얼리어답터 수이고, 단말 노드의 경우 내 자신이 얼리어답터이기 때문에 1이 된다.

그렇다면 그림의 1번에서 예시와 같이 1번 노드의 dp 값은 어떻게 될까?
dp[1][0]은 1번 노드가 일반인일 때를 가정하기 때문에, 자식 노드는 무조건 얼리어답터여야 한다. 따라서 자식 노드가 얼리어답터일 때, 필요한 얼리어답터 수를 전부 더하면 된다.

dp[1][1]은 1번 노드가 얼리어답터일 때인데, 이 경우 자식 노드는 일반인일 수도, 얼리어답터일 수도 있다. 따라서 자식 노드의 dp에서 0, 1번째 값 중 더 작은 값을 가져와 다 더한다. 그리고 마지막으로 1을 더해야하는데 내가 얼리어답터이기 때문이다!

나의 경우 루트를 1로 정하고 1부터 DFS를 통해 트리를 탐색했다. 그리고 최종적으로 dp[1][0] 또는 dp[1][1] 중 더 작은 값을 출력하도록 했다.
그러나 n부터 탐색하고 dp[n]의 값을 사용해도 된다. 왜냐하면 사실 친구 관계는 실제로 계층적인 관계가 아니기도 하고 양방향이기 때문에 어느 곳에서 시작해도 된다!

실제로 이런 문제가 코테에서 나온다면 쉽게 떠올릴 수 있을 것 같지 않다. ㅠㅠ

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

int N;
vector<int> tree[1000000];
// 0: 일반인, 1: 얼리어답터
int dp[1000000][2];
bool visit[1000000] = { false, };

void dfs(int head) {
	dp[head][1] = 1;
	int child;

	for (int i = 0; i < tree[head].size(); i++) {
		child = tree[head][i];
		if (!visit[child]) {
			visit[child] = true;
			dfs(child);
			dp[head][0] += dp[child][1];
			dp[head][1] += min(dp[child][0], dp[child][1]);
		}
	}
}

int main() {
	cin >> N;
	int start, end;
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < N-1; i++) {
		cin >> start >> end;
		tree[start - 1].push_back(end - 1);
		tree[end - 1].push_back(start - 1);
	}
	visit[0] = true;
	dfs(0);

	cout << min(dp[0][0], dp[0][1]) << '\n';
}

소감

음.. 조금 더 발전했다고 할 수 있으려나? 이제 대충 문제를 보면 어떻게 해야겠다는 생각이 든다. 시간이나 입력으로 들어오는 수의 조건 같은 것을 살펴보고 말이다. DP 문제는 코테에서 잘 등장하지 않는다고 한다. 물론 이건 아는 분들의 경험담이긴 한데 코테가 정말 어려운 곳에서나 DP가 나온다고 했다. 그리고 삼성같은 경우는 빡쎈 구현 문제가 자주 등장한다고 했다. 그래서 다음주는 DP말고 다른 유형의 문제를 좀 풀어보고 싶다!!

그리고 이번주는 설 연휴였는데 다행히 다들 취약해지지 않고 끝까지 풀어와서 너무 좋았고 서로 발표하는 세미나도 무사히 끝낼 수 있어서 다행이었다고 생각한다. 아마 학부생 때였으면 6주차까지 이렇게 열심히 꾸려나가지 못했을 거라는 생각이 든다. 방학이 끝나고도 계속 할 것 같은데, 마무리가 언제가 됐든 끝까지 최선을 다하고 싶다.