Codetesing의 코딩공부

크게 어려운것은 없었다.

왼쪽이나 오른쪽 하나를 정해 그쪽부터 채워넣으면 된다.

거리가 먼 것부터 로봇이 물건을 집는다는 뜻이다.

#include<iostream>
#include<string>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

	string in; cin >> in;

	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (in[i] == 'P') {
			for (int j = i - K; j <= i + K; j++) {
				if (j < 0 || i == j || j >= N)
					continue;
				if (in[j] == 'H') {
					in[j] = 'X';
					ans++;
					break;
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

아주 쉬운 문제이다.

한번에 모두 구하려 하지말고 한 번의 점을 구한 후 제곱 해주면 된다.

사각형의 한 변의 길이를 구하려고 봤을때, 점화식을 세우면 A(n) = 2 * A(n - 1) - 1 이 된다.

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	int r = 2;

	for (int i = 0; i < N; i++) {
		r = r * 2 - 1;
	}

	cout << r * r << '\n';

	return 0;
}

생각보다 까다로웠던 문제이다.

내부의 공간은 외부와 차단되어있다는 조건이 까다로웠다.

가장자리엔 얼음이 없다는 조건하에 DFS로 외부의 공기와 내부의 공기를 나누어야했다.

그 후, 외부의 공기와 접촉이 2이상인 얼음은 지우고 다시 내부의 공기를 외부의 공기와 맞는지 DFS하여 확인한다.

이 작업을 반복하여 찾는다.

BFS로 접근하면 더 쉬울꺼 같기도 하고 해설을 확인해봐야겠다.

#include<iostream>
#include<vector>

using namespace std;

#define MAX 101

int N, M;
int map[MAX][MAX];
int ori[MAX][MAX];
bool visited[MAX][MAX] = { false };

int ROTATE_X[] = { -1, 0, 0, 1 };
int ROTATE_Y[] = { 0, 1, -1, 0 };

int trans(int x, int y) {
	
	int cnt = 0;

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + ROTATE_X[i];
		int next_y = y + ROTATE_Y[i];

		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
		{
			cnt++;
			continue;
		}

		if (map[next_x][next_y] == 0)
			cnt++;
	}

	return cnt;
}

bool IS_CLEAR() {

	bool flag = true;
	vector<int> x;
	vector<int> y;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (map[i][j] == 1)
			{
				flag = false;

				if (trans(i, j) >= 2)
				{
					x.push_back(i);
					y.push_back(j);
				}
			}

	for (int i = 0; i < x.size(); i++)
		map[x[i]][y[i]] = 0;

	return flag;
}

void DFS(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int next_x = x + ROTATE_X[i];
		int next_y = y + ROTATE_Y[i];

		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
			continue;

		if (!visited[next_x][next_y] && map[next_x][next_y] == 0)
			DFS(next_x, next_y);
	}
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

	int ans = 0;

	while (1) {

		DFS(0, 0);

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (!visited[i][j] && map[i][j] == 0)
					map[i][j] = 1;

		if (IS_CLEAR())
			break;
		ans++;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
			{
				if (ori[i][j] == 0)
					map[i][j] = 0;
				visited[i][j] = false;
			}
	}

	cout << ans << '\n';

	return 0;
}

완전탐색 문제이다.

DFS로 풀었으며 map의 count를 매개변수로 주었다가 틀렸었다.

매개변수로 줄 필요없이 DFS 함수의 실행 숫자를 세면 그 영역의 넓이가 나온다.

그 외에는 자주 풀던 문제라 어려움 없이 풀 수 있었다.

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

using namespace std;

#define MAX 26

int N;
vector<string> map;
bool visited[MAX][MAX] = { 0 };
vector<int> ans;
int map_cnt = 0;

int ROTATE_X[] = { -1, 0, 0, 1 };
int ROTATE_Y[] = { 0, -1, 1, 0 };

void DFS(int x, int y) {

	visited[x][y] = true;

	map_cnt++;

	for (int i = 0; i < 4; i++) {
		int next_x = x + ROTATE_X[i];
		int next_y = y + ROTATE_Y[i];

		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)
			continue;

		if (!visited[next_x][next_y] && map[next_x][next_y] == '1')
			DFS(next_x, next_y);
	}
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;

	string a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		map.push_back(a);
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (!visited[i][j] && map[i][j] == '1')
			{
				map_cnt = 0;
				DFS(i, j);
				ans.push_back(map_cnt);
			}

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

	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << '\n';

	return 0;
}

이번문제 또한 어려움 없이 반복문으로 푸는 문제이다.

주어진 숫자가 오름차 순인지 내림차 순인지 혼합인지를 판별하는 문제이다.

더 깔끔하게 풀려면 풀 수 있었겠지만 시간차가 없으므로 그냥 풀었다.

#include<iostream>
#include<vector>

using namespace std;

string option(vector<int> a) {

	int opt = 0;

	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] != i + 1)
		{
			opt = 1;
			break;
		}
	}

	if (opt == 0)
		return "ascending";

	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] != a.size() - i)
		{
			opt = 2;
			break;
		}
	}

	if (opt == 2)
		return "mixed";
	else
		return "descending";
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N = 8;
	vector<int> arr(N, 0);

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

	string ans = option(arr);

	cout << ans << '\n';

	return 0;
}