언제나 처음처럼

[문제 링크]

알고리즘 문제해결전략의 비트마스크 부분을 공부하면서 풀게된 첫 문제였다.

주어지는 입력의 범위가 20 미만으로 작기 때문에 최대 32비트 길이의 2진수를 표현할 수 있는 int형 정수의 비트연산을 통해 효율적으로 정답을 구할 수 있다.

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int N, K, M, L;
int preceding[12], classes[10];
int memo[10][1 << 12];

int min(int a, int b) { return a < b ? a : b; }

int BitCount(int taken)
{
	int cnt = 0;

	for (int i = 0; i < N; i++)
		if (taken & (1 << i))
			cnt++;

	return cnt;
}

int Topdown(int semester, int taken)
{
	if (BitCount(taken) >= K) return 0;
	if (semester >= M) return INF;

	int& ret = memo[semester][taken];
	if (ret != 0) return ret;

	ret = INF;

	int canTake = (classes[semester] & ~taken);

	for (int i = 0; i < N; i++)
		if ((canTake & (1 << i)) && (preceding[i] & taken) != preceding[i])
			canTake &= ~(1 << i);

	for (int take = canTake; take > 0; take = ((take - 1) & canTake))
	{
		if(BitCount(take) > L) continue;
		
		ret = min(ret, 1 + Topdown(semester + 1, taken | take));	
	}

	ret = min(ret, Topdown(semester+1, taken));

	return ret;
}

int main(void)
{
	int test_case;
	cin >> test_case;

	while (test_case--)
	{
		memset(preceding, 0, sizeof(preceding));
		memset(classes, 0, sizeof(classes));
		memset(memo, 0, sizeof(memo));

		cin >> N >> K >> M >> L;

		
		for (int i = 0; i < N; i++)
		{
			int R;
			cin >> R;
			
			for (int j = 0; j < R; j++)
			{
				int num;
				cin >> num;
				preceding[i] |= (1 << num);
			}
		}

		for (int i = 0; i < M; i++)
		{
			int C;
			cin >> C;

			for (int j = 0; j < C; j++)
			{
				int num;
				cin >> num;
				
				classes[i] |= (1 << num);
			}
		}

		int result = Topdown(0, 0);

		if (result == INF)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 134 day

[문제 링크]

문제를 이해하는데 있어 어려움을 겪었던 문제였다.

일단, 고속도로에 위치한 센서의 좌표가 정렬되지 않은 상태로 주어지기 때문에 이를 오름차순으로 정렬해야한다.

그리고 집중국의 개수 K가 센서의 개수 N보다 크거나 같으면 센서마다 배치해주면 되지만, 작을 경우 집중국의 수신 가능 영역을 최소로 하기 위해서는 센서 사이의 거리가 긴 센서들을 하나의 집중국에서 연결하는 것을 피해야 한다.

따라서, 인접한 센서들 간의 거리를 구한 다음, 이를 오름차순 정렬하여 거리 차이가 작은 센서들부터 연결하도록 구현하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Greedy(vector<int>& v, int N, int K)
{
	if (K >= N) return 0;

	sort(v.begin(), v.end());

	vector<int> dist(N - 1);
	for (int i = 0; i < N - 1; i++)
		dist[i] = v[i + 1] - v[i];

	sort(dist.begin(), dist.end());

	int ret = 0;
	for (int i = 0; i < N - K; i++)
		ret += dist[i];

	return ret;
}

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

	int K;
	cin >> K;

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

	cout << Greedy(arr, N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 131 day

[문제 링크]

쉬운 문제였음에도 불구하고 고생했던 문제였다.

먼저 정육면체를 만들었을 때 1면이 보이는 주사위, 2면이 보이는 주사위, 3면이 보이는 주사위로 이루어져 있음을 알 수 있다.

또한 이 주사위들의 갯수는 N에 따라 달라지는데 공식은 다음과 같다.

1면이 보이는 주사위의 개수 = (N - 2)^2 * 5 + (N - 2) * 4

2면이 보이는 주사위의 개수 = (N - 2) * 8 + 4

3면이 보이는 주사위의 개수 = 4

따라서 여섯면 중 최솟값, 인접한 2면을 더했을 때 최솟값, 인접한 3면을 더했을 때 최솟값을 각각 구해준 다음 계산해주면 된다.

예외로 N이 1일 때는 주사위 한개만 놓으므로 (6면 전체 값 - 최댓값)이 정답이 된다.

N이 최대 100만이므로 (N-2)^2 연산에서 int 범위를 초과하게 되기 때문에 long long 자료형을 사용했다.

제대로 구현했음에도 불구하고 계속해서 오답을 맞아서 고생했는데, 원인은 변수 N에 있었다.

Greedy() 함수에서 매개변수로 받는 N이 int 형이기 때문에 (N - 2) ^ 2 연산에서 가장 좌측에 있는 N의 자료형을 기준으로 묵시적 형변환되어 오버플로가 발생했던 것이었다.

좌변에 long long 자료형으로 선언한 ret 변수가 있었기 때문에 묵시적 형변환이 일어나지 않을거라 생각하여 디버깅하는데 오래 걸렸던거 같다.

#include <iostream>
using namespace std;

const int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5;
const int INF = 987654321;

int dice[6];
int twoX[12] = { A,A,A,A,B,B,B,C,C,D,D,E };
int twoY[12] = { B,C,D,E,C,D,F,E,F,E,F,F };
int threeX[8] = { A,A,A,A,B,B,C,D };
int threeY[8] = { B,B,C,D,C,D,E,E };
int threeZ[8] = { C,D,E,E,F,F,F,F };

int min(int a, int b) { return a < b ? a : b; }

long long Greedy(int N, int minNum)
{
	int twoSum = INF, threeSum = INF;

	for (int i = 0; i < 12; i++)
		twoSum = min(twoSum, dice[twoX[i]] + dice[twoY[i]]);

	for (int i = 0; i < 8; i++)
		threeSum = min(threeSum, dice[threeX[i]] + dice[threeY[i]] + dice[threeZ[i]]);

	long long one = (long long) (N - 2) * (N - 2) * 5 + (N - 2) * 4;
	long long two = (N - 2) * 8 + 4;
	long long ret = 0;

	ret += one * minNum;
	ret += two * twoSum;
	ret += 4 * threeSum;

	return ret;
}

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

	int maxNum = 0, minNum = INF, sum = 0;

	for (int i = 0; i < 6; i++)
	{
		cin >> dice[i];

		if (N == 1)
		{
			sum += dice[i];
			maxNum = maxNum > dice[i] ? maxNum : dice[i];
		}
		else
			minNum = minNum < dice[i] ? minNum : dice[i];
	}

	if (N == 1)
		cout << sum - maxNum << endl;
	else
		cout << Greedy(N, minNum) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 129 day

[문제 링크]

간단한 그리디 알고리즘 문제였다.

먼저 입력으로 주어지는 문자열에서 같은 숫자로 이루어진 묶음을 하나의 문자로 압축시켰다.

ex) 000/11/00 -> 0 1 0

이렇게 압축한 다음 보았을 때 0과 1중 그 개수가 더 적은 숫자를 뒤집는 것이 곧 최소한의 횟수가 된다는 것을 알 수 있다.

#include <iostream>
#include <string>
using namespace std;

int cnt[2];

int main(void)
{
	string S;
	cin >> S;

	char idx = '2';

	for (int i = 0; i < S.length(); i++)
		if (idx != S[i])
		{
			idx = S[i];
			cnt[S[i] - '0']++;
		}

	int ret = cnt[0] < cnt[1] ? cnt[0] : cnt[1];

	cout << ret << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 129 day

[문제 링크]

입력받은 숫자의 순서를 바꿀 수 없기 때문에 앞에서부터 탐색하여 K가 0이 되기 전까지 가능한 큰 숫자가 앞에 위치하도록 숫자를 지우는 것이 이 문제의 핵심이었다.

입력받은 숫자를 앞에서부터 컨테이너에 담으면서 만약 K가 1이상이고, 앞에 먼저 담은 숫자가 현재 담을 숫자보다 작을 경우 K를 1 감소시키면서 컨테이너에 담긴 숫자를 제거하는 방법으로 구현하였다.

담을 때는 LIFO 방식이 필요하지만, 출력할 때는 FIFO 방식이 필요하므로 deque 컨테이너를 사용하였다.

#include <iostream>
#include <string>
#include <deque>
using namespace std;

void Greedy(string& number, int N, int K)
{
	deque<char> dq;
	
	for (int i = 0; i < N; i++)
	{
		while (!dq.empty() && K != 0 && dq.back() < number[i])
		{
			dq.pop_back();
			K--;
		}

		dq.push_back(number[i]);
	}

	while (K--)
		dq.pop_back();

	while (!dq.empty())
	{
		cout << dq.front();
		dq.pop_front();
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0);

	int N, K;
	cin >> N >> K;

	string number;
	cin >> number;

	Greedy(number, N, K);

	return 0;
}

알고리즘 200일 프로젝트 - 129 day

[문제 링크]

간단한 그리디 알고리즘 문제였다.

학생은 a이상 b이하인 책을 받을 수 있고, 줄 수 있는 책은 1번부터 N번까지 N개 존재한다.

두 학생이 있을 때 서로 a가 같다면 b가 더 큰 학생이 받을 수 있는 책의 범위가 더 넓기 때문에 b가 작은 학생순으로 낮은 번호의 책을 나눠주는 것이 항상 최적해를 보장한다는 것을 알 수 있다.

이를 구현하기 위해 b를 기준으로 오름차순 정렬하고, b의 값이 같을 경우 a가 더 작은 학생이 앞에 가도록 정렬하였다. 그리고 한 학생이 여러권의 책을 받을 수 없기 때문에 check 배열을 통해 책을 받았는지 여부를 확인하였다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

bool check[1000];

int Greedy(vector<pair<int, int>>& student, int N, int M)
{
	sort(student.begin(), student.end());

	int here = 0, cnt = 0;
	
	for (int book = 1; book <= N; book++)
	{
		for (int here = 0; here < M; here++)
		{
			if (student[here].second <= book && student[here].first >= book && !check[here])
			{
				cnt++;
				check[here] = true;
				break;
			}
		}
	}

	return cnt;
}

int main(void)
{
	int test_case;
	cin >> test_case;

	while (test_case--)
	{
		memset(check, 0, sizeof(check));

		int N, M;
		cin >> N >> M;
		
		vector<pair<int, int>> data(M);
		
		for (int i = 0; i < M; i++)
			cin >> data[i].second >> data[i].first;

		cout << Greedy(data, N, M) << endl;
		
		data.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 128 day

[문제 링크]

그리디 알고리즘과 DFS가 섞인 문제였다.

파이프를 연결할 수 있는 경우는 오른쪽 대각선 위, 오른쪽 옆, 오른쪽 대각선 아래 세가지가 있고, 파이프가 서로 겹치거나 엇갈리면 안되기 때문에 대각선 위 -> 옆 -> 아래 순으로 탐색 하는 것이 항상 최적해를 보장한다.

성공적으로 파이프를 연결했다면 1을 반환하고, 파이프가 연결되었기 때문에 다른 경우는 고려할 필요 없이 탐색을 종료한다.

한번 방문했던 좌표는 그전에 이미 시도해본 좌표이기 때문에 고려해줄 필요가 없다. 따라서 2차원 visit 배열을 선언하여 방문여부를 체크했다.

#include <iostream>
#include <string>
using namespace std;

string board[10000];
bool visit[10000][500];
int dy[3] = { -1, 0, 1 };

int Greedy(int startY, int startX, int R, int C)
{
	if (startX == C - 1) return 1;

	int ret = 0;

	for (int i = 0; i < 3; i++)
	{
		int nextY = startY + dy[i];
		int nextX = startX + 1;

		if (nextY >= 0 && nextY < R && board[nextY][nextX] != 'x' && !visit[nextY][nextX])
		{
			visit[nextY][nextX] = true;
			ret = Greedy(nextY, nextX, R, C);
		}

		if (ret == 1)
			break;
	}

	return ret;
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int R, C;
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		cin >> board[i];

	int cnt = 0;
	for (int i = 0; i < R; i++)
		cnt += Greedy(i, 0, R, C);

	cout << cnt << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 126 day

[문제 링크]

문제 풀이법을 떠올리기가 쉽지않았던 문제였다.

플로이드 와샬 알고리즘을 이용하는 문제였는데, 필자는 도시 A에서 도시 B로 이동하는데 걸리는 최소 시간을 비교함에 있어 도시 A에서 도시 C를 거쳐 도시 B로 가는 경우 뿐만 아니라 도시 A에서 도시 C를 거치고 도시 D를 거쳐 도시 B로 이동하는 시간이 더 짧을수도 있다고 생각하고 풀어서 정답을 출력할 수 없었다.

입력으로 주어지는 행렬이 각 도시에서 도시로 이동하는 최소 시간이기 때문에 도시 A에서 도시 B로 이동하는데 걸리는 최소 시간과 A와 B를 제외한 다른 도시를 경유해서 가는데 걸리는 최소 시간을 비교하여 걸리는 시간이 같을 경우 A->B로 연결되는 도로는 사용할 필요가 없으므로 제거하고, 다른 도시를 경유해서 가는데 걸리는 최소 시간이 더 짧을 경우 입력으로 받은 행렬이 잘못 주어진 것이므로 옳은 결과를 얻는 것이 불가능하다.

모든 도시를 경유해서 갔지만 위 두가지 경우에 해당하지 않는다면 다른 길이 존재하지 않는 것이므로 A->B로 연결되는 도로를 사용해야 한다.

#include <iostream>
#include <cstring>
using namespace std;

int city[20][20];
bool check[20][20];

int Greedy(int N)
{
	memset(check, 1, sizeof(check));

	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			for (int k = 0; k < N; k++)
			{
				if (i == j || i == k || j == k)
					continue;

				if (city[i][j] == city[i][k] + city[k][j])
				{
					check[i][j] = false;
					check[j][i] = false;
				}
				else if (city[i][j] > city[i][k] + city[k][j])
					return -1;
			}

	return 0;
}

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

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

	int sum = Greedy(N);

	if (sum == -1)
	{
		cout << "-1" << endl;
		return 0;
	}
	else
	{
		for (int i = 0; i < N; i++)
			for (int j = i+1; j < N; j++)
				if (check[i][j])
					sum += city[i][j];

		cout << sum << endl;
		return 0;
	}
}

알고리즘 200일 프로젝트 - 125 day