21년 8월 알고리즘 스터디 4주차

15685번 : 드래곤 커브

---

    K 가 1 초과이니 경우, K 세대 드래곤 커브는 K-1 세대 드래곤 커브를 끝점을 기준으로 -90도 회전시킨 다음, 그것을 끝 점에 붙인 것이라고 한다. d 가 0~3 일 때, 각각 오른쪽, 위, 왼쪽, 아래인데 이것들을 90도 회전시키면 걸 d' 이라고 한다면 d' 은 위, 왼쪽, 아래, 오른쪽으로 d 를 기준으로 1, 2, 3, 0 이다. 따라서 -90도 회전시킨 d = (d' + 1) % 4 라는 걸 알 수 있다.

 

    prev_move 벡터에 이전 세대에 움직였던 방향들을 넣어두고, 역순으로 -90도 회전해서 적용하면 다음 세대 드래곤 커브가 된다.

 

    정사각형의 경우 네 꼭짓점이 true 여도, 한 변이 비어있을 수 있어 고민했었는데, 문제를 다시 읽어보니 네 꼭짓저머이 드래곤 커브의 일부이기만 하면 된다고 해서 단순하게 다 true 인지 확인한 뒤 ++ans 해줬다.

 

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	int N, x, y, d, g, move_size, ans;
	vector<vector<bool>> board(101, vector<bool>(101, false));

    // 이전에 어떻게 움직였는지 저장하는 벡터
	vector<int> prev_move;

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

	cin >> N;

	ans = 0;

	while (N--)
	{
		prev_move.clear();

		cin >> x >> y >> d >> g;

		board[y][x] = true;
		y += dy[d];
		x += dx[d];
		board[y][x] = true;
		prev_move.push_back(d);

		while (g--)
		{
			move_size = prev_move.size();

			for (int i = move_size - 1; i >= 0; --i)
			{
				y += dy[(prev_move[i] + 1) % 4];
				x += dx[(prev_move[i] + 1) % 4];

				board[y][x] = true;
				prev_move.push_back((prev_move[i] + 1) % 4);
			}
		}
	}

	for (int i = 0; i < 100; ++i)
	{
		for (int j = 0; j < 100; ++j)
		{
			if (board[i][j] && board[i + 1][j] && board[i][j + 1] && board[i + 1][j + 1])
			{
				++ans;
			}
		}
	}

	cout << ans << '\n';
}

 

 

5557번 : 1학년

---

    엄청 삽질한 문제. 첫 번째는 무조건 쓰이고, 마지막은 등호로 고정인데 이걸 생각 안 하고 풀다가 오래 걸렸다. cache 에 몇 번째 숫자까지 계산했는지와 지금까지의 합을 확인하도록 구현했다. 마지막 등호의 경우, N-1 까지의 합, val 이 마지막 수 num[N-1] 과 같으면 한 가지 경우의 수로 고려되도록 했다.

 

    문제를 풀다가 cache 의 인덱스를 비트 연산자를 이용해서 1차원으로 구현할 수 있을 것 같았다. '+' 의 경우 1, '-' 의 경우 0으로 생각해서, n 번째 숫자까지 계산했다면, n+1 번째 숫자는 덧셈인 경우에는 1<<n + 1. 뺼셈인 경우에는 1<<n + 0 으로 계산해서 넘겨주면 됐는데 계속 오류가 나서 확인해보니 long long 자료형을 넘어가서 이 문제에는 적합하지 않았다. 최대 (2^101)-1 이 되는데 long long 의 최댓값은 (2^63)-1 이기에 안 된다. N 의 최댓값이 60 정도였다면 가능했을 것 같다.

 

스터디 후기

 

    cache 를 1 차원만 써서 합 val 이 나오는 경우의 수를 저장한 뒤, 마지막에 N-1 번째 cache 값을 확인하면 효율적으로 풀 수 있다.

 

#include <iostream>

using namespace std;

int N;
int num[101];
// cache[몇 번째 숫자까지 계산했는지][지금까지의 합]
long long cache[101][21];

long long dp(int n, int val)
{
	if (n == N-1)
	{
		if (val == num[N-1])
		{
			return 1;
		}

		else
		{
			return 0;
		}
	}

	if (cache[n][val] != -1)
		return cache[n][val];

	long long cnt = 0;

	if (val + num[n] <= 20)
		cnt += dp(n+1, val + num[n]);

	if (val - num[n] >= 0)
		cnt += dp(n+1, val - num[n]);

	return cache[n][val] = cnt;
	
}

int main(void)
{
	cin >> N;

	fill(&cache[0][0], &cache[100][20], -1);

	for (int i = 0; i < N; ++i)
		cin >> num[i];

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

 

 

2470번 : 두 용액

---

    이것도 푸는데 오래 걸린 문제이다. 처음에는 문제를 보자마자 각 값에 -1 을 곱해서 이 값을 lower_bound, upper_bound 로 찾아준 뒤 합의 절댓값이 최소가 되는 값을 찾아서 pair 로 저장한 뒤에 출력하면 될 줄 알았다. 그런데 -1 배한 값이 모든 값보다 큰 경우 liq.size() 가, 모든 값보다 작은 경우 -1 이 반환이 돼서 인덱스 범위를 넘어가 오류가 생겼다. 예외 처리 다 해줬는데 안 되길래 머리 아파서 다 갈아엎고, 알고리즘 분류에서 두 포인트 있는 거 확인하고 두 포인트로 풀었다.

 

스터디 후기

 

    lower_bound 는 이하가 아니라 이상이고, upper_bound 는 초과이다. 함수를 잘못 이해해서 삽질한거였다 ㅠㅠ 라이브러리를 쓰기 전에 알던 거라도 다시 한 번 알아보고 쓰자. 그리고 질문할 때 좋게 말한다고 해도 공격적으로 들릴 수 있으니 사전에 코드를 읽고 질문을 준비한 다음에 조심히 물어보자. 동아리 면접 포폴 만든다고 시간이 없어서 코드를 미리 못 읽어온 게 실책이였다 ㅠㅠ

 

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

using namespace std;

int main(void)
{
	int N, min_diff, s, e;
	pair<int, int> ans;
	vector<int> liq;

	cin >> N;

	liq.assign(N, 0);
	min_diff = 2147483647;

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

	sort(liq.begin(), liq.end());
	
	s = 0;
	e = N - 1;

	while (s < e)
	{
		if (abs(liq[s] + liq[e]) < min_diff)
		{
			min_diff = abs(liq[s] + liq[e]);
			ans = { liq[s], liq[e] };

			if (min_diff == 0)
				break;
		}

		else if (liq[s] + liq[e] > 0)
			--e;

		else
			++s;
	}

	cout << ans.first << ' ' << ans.second << '\n';
}

 

 

10451번 : 순열 사이클

---

    dfs 로 방문한 적있는 노드를 만난다면 순환 사이클이라고 판단하게 구현해서 해결했다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> adj;
vector<bool> visited;

bool dfs(int n)
{
	bool flag = false;

	visited[n] = true;

	for (int i = 0; i < adj[n].size(); ++i)
	{
		if (!visited[adj[n][i]])
			flag = dfs(adj[n][i]);

		else
			flag = true;
	}

	return flag;
}

int main(void)
{
	int T, N, input, ans;

	cin >> T;

	while (T--)
	{
		ans = 0;
		adj.assign(1001, vector<int>());
		visited.assign(1001, false);

		cin >> N;

		for (int i = 1; i <= N; ++i)
		{
			cin >> input;
			adj[i].push_back(input);
		}

		for (int i = 1; i < 1001; ++i)
		{
			if (!visited[i])
			{
				if (dfs(i))
					++ans;
			}
		}

		cout << ans << '\n';
	}
}

 

 

1303번 : 전투

---

    isW boolean 값으로 확인하는 대상이 아군인지 적군인지 판단해서, 뭉쳐있는 수를 반환한 뒤 pow 함수로 제곱해서 처리했다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<vector<char>> field;
vector<vector<bool>> visited;

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

int N, M, w_power, b_power;

int dfs(int x, int y, bool isW)
{
	int cnt = 0;
	
	visited[y][x] = true;

	for (int i = 0; i < 4; ++i)
	{
		if (x + dx[i] < 0 || x + dx[i] >= N || y + dy[i] < 0 || y + dy[i] >= M)
			continue;

		if (!visited[y + dy[i]][x + dx[i]])
		{
			if (isW && field[y + dy[i]][x + dx[i]] == 'W')
					cnt += dfs(x + dx[i], y + dy[i], isW);

			else if (!isW && field[y + dy[i]][x + dx[i]] == 'B')
				cnt += dfs(x + dx[i], y + dy[i], isW);
		}
	}

	return 1 + cnt;
}

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

	field.assign(M, vector<char>(N));
	visited.assign(M, vector<bool>(N, false));

	w_power = b_power = 0;

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

	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (!visited[i][j])
			{
				if (field[i][j] == 'W')
				{
					w_power += pow(dfs(j, i, true), 2);
				}

				else
				{
					b_power += pow(dfs(j, i, false), 2);
				}
			}
		}
	}

	cout << w_power << ' ' << b_power << '\n';
}

 

 

2212번 : 센서

---

    주어진 센서를 정렬한 뒤, 다음 센서와의 거리를 계산해봤다. 예제의 경우 '2 3 0 1 2' 인데 거리 하나를 고려하지 않으려면 집중국이 2개가 필요하다. Ex) 1 -2- 3 -3- 6 -0- 6 -1- 7 -2- 9 인 경우, 가장 거리가 먼 3과 6 에 있는 센서 사이를 나눠 막는다고 생각해보면 영역이 2개가 되기에 집중국도 2개가 필요하다. (1 -2- 3) -/- (6 -0- 6 -1- 7 -2- 9 ) 이렇게 생각해서 거리가 가장 긴 부분 x 개를 없애면 집중국의 개수 k 가 x+1 개 필요하게 되고, 주어진 최대 집중국의 개수가 K 개이니 K = X + 1 -> X = K - 1. 최대로 막을 수 있는 횟수는 K-1 번이다. 따라서 센서 사이의 거리를 내림차순으로 정렬한 뒤 K-1 번 pop_front() 해주고, 남은 값들을 모두 더하면 수신 가능 영역 길이의 합의 최솟값이 나온다.

 

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main(void)
{
	int N, K, ans;
	deque<int> sensor, dist;

	cin >> N >> K;

	sensor.assign(N, 0);
	dist.assign(N - 1, 0);
	ans = 0;
	
	for (int i = 0; i < N; ++i)
	{
		cin >> sensor[i];
	}

	if (K < N)
	{
		sort(sensor.begin(), sensor.end());

		for (int i = 0; i < N - 1; ++i)
		{
			dist[i] = sensor[i + 1] - sensor[i];
		}

		sort(dist.begin(), dist.end(), greater<int>());

		// 길이가 가장 긴 것 하나 막으면 전파국 2개, x개 막으면 전파국 x+1 개
		// k 가 최대 전파국 개수. k = x + 1, x = k - 1.
		for (int i = 1; i < K; ++i)
		{
			dist.pop_front();
		}

		for (int i = 0; i < dist.size(); ++i)
		{
			ans += dist[i];
		}
	}

	cout << ans << '\n';
}