취미로 코딩하기

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

이번에 볼 문제는 백준 32871번 문제인 돌 게임 nm이다.
문제는 아래 링크를 확인하자.

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

n행 m열의 돌에서 어떤 행을 지우더라도 n-1행 m열의 돌이 놓여있는 상황과 같아지고, 어떤 열을 지우더라도 n행 m-1열의 돌이 놓여있는 상황과 같아짐을 관찰하자. 또한 행 또는 열이 하나만 남아있다면 그 행 또는 열을 지우는 것으로 항상 이길 수 있다는 점을 관찰하자.

위의 관찰을 이용하면 2행2열의 상황에서는 어떤 행 또는 열을 지워도 해당 차례에 돌을 가져가는 사람이 지게 된다. 또한 그렇지 않은 경우 항상 행 또는 열이 하나만 남게 되는 상황을 피해 돌을 가져갈 수 있다.

남은 경우 중에서 행과 열의 합이 홀수인 경우 어떻게 행동을 하더라도 행과 열의 합이 짝수가 되며, 행과 열의 합이 짝수이고 2행2열이 아닌 경우 어떻게 행동을 하더라도 행과 열의 합이 홀수가 되므로, 앞서 분류한 상황을 제외하면 행과 열의 합이 홀수인 경우 해당 차례에 돌을 가져가는 사람이 이기고 그렇지 않을 경우 해당 차례에 돌을 가져가는 사람이 진다는 점을 알 수 있다.

이를 이용하여 문제를 해결하자.

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

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

int T;
ll N, M;

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

	cin >> T;
	while (T--) {
		cin >> N >> M;
		if (N == 1 || M == 1 || ((N + M) & 1)) cout << "YES\n";
		else cout << "NO\n";
	}
}

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

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

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

하나의 칩을 먹는 데에 1분이 필요하고 빈 캔을 하나 만드려면 최소한 한 캔에 들어있는 칩의 개수인 \(n\)개의 칩은 먹어야 할 것이므로, 빈 캔을 마주할 수 있는 가장 빠른 시간은 \(n+1\)분이 된다.

칩을 먹을 수 있다면 매번 칩을 먹어 빈 캔을 마주하지 않을 수 있고 칩은 총 \(kn\)개 있으므로, 빈 캔을 마주할 수 있는 가장 늦은 시간은 \(kn+1\)분이 된다.

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

#include <iostream>
using namespace std;

int A, B;

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

	cin >> A >> B;
	cout << B + 1 << ' ' << A * B + 1;
}

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

이번에 볼 문제는 백준 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;
}