취미로 코딩하기

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

이번에 볼 문제는 백준 32916번 문제인 Another Brick in the Wall이다.
문제는 아래 링크를 확인하자.

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

\(l\)이 홀수일 경우 각 층에는 길이 3의 벽돌이 적어도 하나씩 필요하다. 따라서 최소한 층의 개수와 같은 만큼의 벽돌을 사용해야 함을 알 수 있다. 또한 그 길이 3의 벽돌을 한 쪽 끝과 다른 쪽 끝에 층마다 번갈아 두면서 쌓으면 항상 조건을 만족하는 벽돌 배치를 얻을 수 있다. 따라서 \(l\)이 홀수일 경우 답은 \(h\)와 같다.

\(l\)이 6 이상의 짝수일 경우 \(h\)가 1이면 그 층을 길이 2의 벽돌만으로 채울 수 있으므로 답은 0이다. \(h\)가 2인 경우 (1) 1층을 길이 2의 벽돌만으로 쌓은 경우 못해도 맨 왼쪽과 맨 오른쪽에는 길이 3의 벽돌을 사용하지 않으면 조건을 만족시키지 못하므로 최소 2개의 길이 3 벽돌이 필요하며, (2) 1층을 길이 2의 벽돌만으로 쌓지 않았을 경우에도 \(l\)이 홀수이므로 최소 2개의 길이 3 벽돌이 필요하다. 따라서 답은 2 이상이 됨을 알 수 있다. 그리고 실제로 (1)과 같이 쌓은 뒤 남은 곳을 길이 2 벽돌로 채우면 조건을 만족하는 벽돌 배치를 항상 얻을 수 있으므로 \(h\)가 2인 경우의 답은 2이다.

\(h\)가 3 이상의 경우 맨 위의 두 층을 제거하고 생각할 때 그 위의 두 층을 채우려면 2개의 길이 3 벽돌이 필요하며, 위에서 구한 2층의 배치를 반복하는 것으로 그 개수로 층을 항상 쌓을 수 있음을 알 수 있다. 따라서 \(l\)이 짝수일 경우의 답은 홀수일 경우 \(h\)에서 1을 뺀 수, 아니라면 \(h\)와 같다.

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

#include <iostream>
using namespace std;

int L, H;

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

	cin >> L >> H;
	if (L & 1) cout << H;
	else cout << H / 2 * 2;
}

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

이번에 볼 문제는 백준 32760번 문제인 Nothing Everything이다.
문제는 아래 링크를 확인하자.

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

\(i\)번 정점에서 E 연산을 수행하면 \(i\)보다 작은 번호를 가진 정점과 \(i\)를 잇는 모든 간선이 추가되고, N 연산을 수행하면 이러한 모든 간선이 추가되지 않음을 관찰하자.

따라서, 각 정점마다 그 정점보다 작은 번호로 이어진 간선이 총 몇 개 존재하는지 세어 각각 N 또는 E 연산으로 해당 에지들을 추가할 수 있는지 판단하는 것으로 문제를 해결할 수 있다.

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

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

int N, M;
int cnt[100001];
string ans;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		if (x > y) cnt[x]++;
		else cnt[y]++;
	}

	for (int i = 2; i <= N; i++) {
		if (!cnt[i]) ans += 'N';
		else if (cnt[i] == i - 1) ans += 'E';
		else {
			cout << -1;
			return 0;
		}
	}
	cout << ans;
}

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

이번에 볼 문제는 백준 32752번 문제인 수열이에요?이다.
문제는 아래 링크를 확인하자.

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

수의 배치를 바꿔 얻은 수열이 단조증가수열이라면 그 배치한 수들 또한 단조증가하는 순서대로 나열되어야 함을 관찰하자.

따라서 다시 배치할 수들을 단조증가하는 순서대로 먼저 나열해두고, 주어진 배열이 단조증가수열인지 확인하는 것으로 문제를 해결할 수 있다. 이는 정렬을 통해 어렵지 않게 해낼 수 있다.

주어진 구간의 수의 최댓값과 최솟값을 구하고 (존재한다면) 주어진 구간의 앞의 값 및 뒤의 값과 비교하면 더 개선된 시간복잡도로도 문제를 해결할 수 있다.

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

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

int N, L, R;
int A[100000];

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

	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A + L - 1, A + R);
	for (int i = 0; i + 1 < N; i++) {
		if (A[i] > A[i + 1]) {
			cout << 0;
			return 0;
		}
	}
	cout << 1;
}

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

이번에 볼 문제는 백준 32775번 문제인 가희와 4시간의 벽 1이다.
문제는 아래 링크를 확인하자.

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

주어진 수를 1회 타노스할 때마다 길이가 \(2^{-1}\)배가 됨을 관찰하자. 따라서 길이가 \(2^N\)을 \(T\)번 타노스하면 만들어지는 수의 길이는 \(2^{N-T}\)가 됨을 알 수 있다.

위의 관찰을 통해 잘 생각해보면 주어진 수의 결과는 앞에서부터 \(N-T\)자씩 끊어 읽은 수 중 하나가 됨을 알 수 있다. 이 중 가장 큰 수를 찾아 문제를 해결하자.

이 때, 주어지는 수 자체의 크기가 매우 크므로 그 값을 직접 저장하기는 곤란할 수 있다. 대신 수를 문자열의 형태로 저장하고 문자열의 대소 비교를 이용해 가장 큰 문자열을 찾는 식으로 구현할 수 있다. 자릿수가 같은 두 수의 크기 비교는 문자열의 비교 결과와 같다는 점을 상기하자.

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

#include <iostream>
using namespace std;

int N, T;
string ans;
string s;

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

	cin >> N >> T;
	T = N - T;
	N = (1 << N), T = (1 << T);
	N /= T;
	while (N--) {
		s.clear();
		for (int t = 0; t < T; t++) {
			char c; cin >> c;
			s += c;
		}
		ans = max(ans, s);
	}
	cout << ans;
}

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

이번에 볼 문제는 백준 32775번 문제인 가희와 4시간의 벽 1이다.
문제는 아래 링크를 확인하자.

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

지문을 잘 이해하는지 묻는 문제이다. 지문을 잘 읽으면 \(S_{ab}\)보다 \(F_{ab}\)가 작다면 항공편을 더 많이 이용할 것이고 아니라면 고속철도를 더 많이 이용할 것임을 알 수 있다.

이를 이용해 문제를 해결하자. 이는 조건문을 이용하는 것으로 간단히 구현할 수 있다.

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

#include <iostream>
using namespace std;

int x, y;

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

	cin >> x >> y;
	if (x > y) cout << "flight";
	else cout << "high speed rail";
}

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

이번에 볼 문제는 백준 32715번 문제인 십자 찾기이다.
문제는 아래 링크를 확인하자.

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

각 칸마다 해당 칸에서부터 상하좌우로 연속으로 몇 칸씩 모눈이 색칠되어있는지를 안다면 문제를 쉽게 해결할 수 있을 것이다. 그러나 각 칸에서 직접 연속된 칸을 방향별로 세는 것은 좋은 전략은 아닌데, 모든 모눈이 색칠되어있는 등 극단적인 경우 실행시간이 오래 걸릴 수 있기 때문이다.

prefix sum을 이용해 방향별로 몇 칸이 연속 색칠되어있는지 미리 전처리를 해 실행시간을 줄이자.

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

#include <iostream>
using namespace std;

int R, C, K, ans;
short A[2502][2502][4];

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

	cin >> R >> C >> K;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> A[r][c][0];
			A[r][c][1] = A[r][c][2] = A[r][c][3] = A[r][c][0];
		}
	}
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (A[r][c][0]) A[r][c][0] += A[r][c - 1][0];
		}
	}
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (A[r][c][1]) A[r][c][1] += A[r - 1][c][1];
		}
	}
	for (int r = R; r > 0; r--) {
		for (int c = C; c > 0; c--) {
			if (A[r][c][2]) A[r][c][2] += A[r][c + 1][2];
		}
	}
	for (int r = R; r > 0; r--) {
		for (int c = C; c > 0; c--) {
			if (A[r][c][3]) A[r][c][3] += A[r + 1][c][3];
			if (A[r][c][0] > K && A[r][c][1] > K && A[r][c][2] > K && A[r][c][3] > K) ans++;
		}
	}

	cout << ans;
}