취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2713번 문제인 규현이의 사랑을 담은 문자메시지이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열을 문제가 요구하는 형태로 바꿔 출력하는 구현문제이다.

입력으로 주어지는 문자열은 getline을 이용해 큰 문제없이 읽을 수 있다.

소용돌이 패턴의 구현은 visited 배열을 이용하면 "오른쪽으로 이동할 수 있을 때까지 이동", "아래로 이동할 수 있을 때까지 이동", "왼쪽으로 이동할 수 있을 때까지 이동", "위쪽으로 이동할 수 있을 때까지 이동"을 반복하는 것으로 어렵지 않게 구현할 수 있다.

아래는 제출한 소스코드이다.

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

int T, R, C;
string s, ss;
int ans[23][23];
int visited[23][23];

void solve() {
	memset(ans, 0, sizeof(ans));
	memset(visited, 0, sizeof(visited));

	ss = "";
	cin >> R >> C;
	getline(cin, s); s = s.substr(1, s.length() - 1);
	for (int r = 0; r <= R + 1; r++) visited[r][0] = visited[r][C + 1] = 1;
	for (int c = 0; c <= C + 1; c++) visited[0][c] = visited[R + 1][c] = 1;

	for (auto& l : s) {
		int x = l - 'A' + 1;
		string tmp = "";
		for (int i = 0; i < 5; i++) {
			if (x & 1) tmp += "1";
			else tmp += "0";
			x >>= 1;
		}

		while (!tmp.empty()) {
			ss += tmp.back();
			tmp.pop_back();
		}
	}

	while (ss.length() < R * C) ss += "0";

	int r = 1, c = 0, idx = 0;
	while (idx < R * C) {
		while (!visited[r][c + 1]) {
			c++;
			visited[r][c] = 1;
			ans[r][c] = ss[idx++];
		}
		while (!visited[r + 1][c]) {
			r++;
			visited[r][c] = 1;
			ans[r][c] = ss[idx++];
		}
		while (!visited[r][c - 1]) {
			c--;
			visited[r][c] = 1;
			ans[r][c] = ss[idx++];
		}
		while (!visited[r - 1][c]) {
			r--;
			visited[r][c] = 1;
			ans[r][c] = ss[idx++];
		}
	}

	for (int rr = 1; rr <= R; rr++) {
		for (int cc = 1; cc <= C; cc++) cout << (char)(ans[rr][cc]);
	}
	cout << '\n';
}

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

	cin >> T;
	while (T--) solve();
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2718번 문제인 타일 채우기이다.
문제는 아래 링크를 확인하자.

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

간단한 점화관계를 찾아 문제를 해결해보자.

4행K열의 타일에 대하여 다음과 같은 수열을 정의하자:

A1234[k]: 주어진 타일을 도미노로 모두 채울 경우의 수

A12[k]: 주어진 타일을 마지막 열의 3번 행과 4번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

A23[k]: 주어진 타일을 마지막 열의 4번 행과 1번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

A34[k]: 주어진 타일을 마지막 열의 1번 행과 2번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

A41[k]: 주어진 타일을 마지막 열의 2번 행과 3번 행의 칸을 제외한 모든 칸을 도미노로 채울 경우의 수

이 때, 4행K열 타일의 마지막 열을 어떤 식으로 채우느냐를 생각하는 것으로 다음과 같이 점화식을 세울 수 있다:

A12[i] = A1234[i - 1] + A34[i - 1] // 1행과 2행에 걸친 2x1 도미노를 배치 or 1행과 2행에 각각 1x2 도미노를 배치
A34[i] = A1234[i - 1] + A12[i - 1] // 위와 같은 방식
A23[i] = A1234[i - 1] + A41[i - 1] // 위와 같은 방식
A41[i] = A23[i - 1] // 위와 같은 방식, 4행과 1행에 동시에 걸치게끔 2x1 도미노를 놓을 수는 없음에 유의
A1234[i] = A1234[i - 1] + A12[i - 1] + A34[i - 1] + A23[i - 1] + A1234[i - 2] // 1x2 도미노를 배치하는 경우들을 생각해보면 어렵지 않게 떠올릴 수 있을 것이다.

위의 점화식을 이용해 문제를 해결하자.

A13 또는 A24와 같은 수열은 정의하지 않았는데, 이와 같은 경우는 존재하지 않기 때문이다. A13과 같은 모양의 이전 단계는 A24이어야 하고 A24와 같은 모양의 이전 단계는 A13이어야 하므로 초기상태에서 도달할 수 없음을 관찰하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int T;
ll A12[22], A23[22], A34[22], A41[22], A1234[22];

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

	A1234[0] = 1;
	A12[1] = 1, A34[1] = 1, A23[1] = 1, A1234[1] = 1;
	for (int i = 2; i < 22; i++) {
		A12[i] = A1234[i - 1] + A34[i - 1];
		A34[i] = A1234[i - 1] + A12[i - 1];
		A23[i] = A1234[i - 1] + A41[i - 1];
		A41[i] = A23[i - 1];
		A1234[i] = A1234[i - 1] + A12[i - 1] + A34[i - 1] + A23[i - 1] + A1234[i - 2];
	}

	cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << A1234[x] << '\n';
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15311번 문제인 약 팔기이다.
문제는 아래 링크를 확인하자.

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

1을 1000개 나열한 수열의 첫 원소부터 i번째 원소까지의 합은 항상 i가 됨을 관찰하자.

또한, 1000을 1000개 나열한 수열의 첫 원소부터 j번째 원소까지의 합은 항상 1000j가 됨을 관찰하자.

이와 같은 두 관찰을 이용하면 위의 두 수열을 이어붙인 수열에서는 1 이상 100만 이하의 모든 수에 대하여 합이 그 수인 연속 부분수열을 어렵지 않게 찾을 수 있음을 알 수 있다. 해당 수열은 문제의 조건을 만족하므로 이를 출력해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

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

	cout << 2000 << '\n';
	for (int i = 0; i < 1000; i++) cout << 1 << ' ';
	for (int i = 0; i < 1000; i++) cout << 1000 << ' ';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7286번 문제인 Ancient Keyboard이다.
문제는 아래 링크를 확인하자.

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

1000 이하의 각 음이 아닌 정수시각에 대하여 각 시각에 켜져있는 키의 개수를 구하는 것으로 문제를 해결하자.

이는 각 시각마다 불이 켜져있는 키의 개수를 저장할 배열을 만들고, 각 키마다 켜져있는 각 시각에 켜져있는 키의 개수를 1씩 더하는 것으로 구할 수 있다.

아래는 제출한 소스코드이다.

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

int T, N;
int arr[1001];

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

	cin >> T;
	while (T--) {
		memset(arr, 0, sizeof(arr));
		cin >> N;
		while (N--) {
			char c; int L, R; cin >> c >> L >> R;
			while (L < R) arr[L++]++;
		}
		for (int i = 0; i < 1001; i++) {
			if (arr[i]) cout << (char) ('A' + arr[i] - 1);
		}
		cout << '\n';
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2508번 문제인 사탕 박사 고창영이다.
문제는 아래 링크를 확인하자.

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

주어지는 행렬에서 "행 방향으로 인접한 세 문자가 '>' 'o' '<'인 위치의 개수" 및 "열 방향으로 인접한 세 문자가 'v' 'o' '^'인 위치의 개수"를 직접 세어 문제를 해결할 수 있다.

살펴볼 인접한 위치의 개수는 \(O(RC)\)개이고, 각 위치를 살펴볼 때 한번에 3개의 원소(\(O(1)\))만을 살펴보면 되므로 이와 같은 해법의 시간복잡도는 \(O(RC)\)와 같다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T;
int R, C;
string board[400];

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

	cin >> T;
	while (T--) {
		int ans = 0;
		cin >> R >> C;
		for (int r = 0; r < R; r++) cin >> board[r];

		for (int r = 0; r < R; r++) {
			for (int c = 0; c + 2 < C; c++) {
				if (board[r][c] == '>' && board[r][c + 1] == 'o' && board[r][c + 2] == '<') ans++;
			}
		}

		for (int c = 0; c < C; c++) {
			for (int r = 0; r + 2 < R; r++) {
				if (board[r][c] == 'v' && board[r + 1][c] == 'o' && board[r + 2][c] == '^') ans++;
			}
		}

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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2097번 문제인 조약돌이다.
문제는 아래 링크를 확인하자.

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

각 변의 길이가 정수이고 둘레가 일정한 직사각형은 모든 변의 길이의 차이가 최소화될 때 포함하는 격자점의 수가 최대가 된다는 사실은 잘 알려져있다.

위 사실을 이용해 직사각형의 x축 방향 길이와 y축 방향의 길이를 1부터 시작해 번갈아가며 1씩 늘리면서 N개의 격자점을 포함하기 시작하는 순간을 찾아내 문제를 해결할 수 있다.

위와 같이 길이를 늘려나갈 경우 직사각형이 포함하는 점의 개수는 변의 길이를 늘린 횟수의 제곱에 비례하므로 이 방법으로 문제를 해결하는 알고리즘은 \(O(\sqrt{N})\)에 동작한다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N;
ll x = 1, y = 1;

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

	cin >> N;
	while (1) {
		if ((x + 1) * (y + 1) >= N) break;
		x++;
		if ((x + 1) * (y + 1) >= N) break;
		y++;
	}

	cout << (x + y) * 2;
}