취미로 코딩하기

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

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

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

이번에 볼 문제는 백준 32710번 문제인 구구단표이다.
문제는 아래 링크를 확인하자.

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

주어진 수가 2단부터 9단까지의 구구단표에 등장하는지(단, 곱해진 결과값만이 아닌 곱하는 수도 등장하는 수에 포함된다) 여부를 판단하는 문제이다.

직접 구구단을 하듯이 반복문을 작성하여 주어진 수가 등장하는지 확인하는 것으로 문제를 충분히 해결할 수 있다.

1은 구구단의 결과값으로 등장하지 않지만 표에는 등장한다는 점에 유의하자.

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

#include <iostream>
using namespace std;

int N;
bool visited[101];

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

	cin >> N;
	for (int i = 1; i < 10; i++) {
		visited[i] = 1;
		for (int j = 1; j < 10; j++) {
			visited[i * j] = 1;
		}
	}
	if (visited[N]) cout << 1;
	else cout << 0;
}

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

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

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

먼저 두 수 중 더 작은 수의 앞에 leading zero를 추가해 자릿수를 같게 해두자.

이제, 가장 앞자리부터 살피면서 서로 다른 자릿수가 나올 때까지는 해당 자리의 수가 1일 경우 그에 대응되는 액면가의 화폐를 집합에 포함하고, 그렇지 않다면 다음 자리로 넘어가자. 해당 자리가 둘 다 0이면 아무 문제 없고, 1이면 모든 액수를 구성하는 데에 그 자리에 해당하는 액면가의 화폐가 필요할 것이며 나머지 자리들은 해당 자리를 지워 얻은 두 수 사이의 수를 표현할 수 있으면 되기 때문이다.

처음으로 다른 값이 나온 자리가 있을 경우, 해당 자리가 1인 수가 존재할 수밖에 없으며 그 자리가 0이고 이후의 자리가 모두 1인 수 또한 항상 표현이 가능해야 하므로 해당 자리를 포함한 모든 자리에 대응되는 액면가의 화폐가 필요함을 알 수 있다.

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

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

int N, ans;
string A, B, s;

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

	cin >> B >> A;
	while (A.length() > B.length() + s.length()) s += '0';
	s += B;
	swap(B, s);
	N = A.length();
	for (int i = 0; i < N; i++) {
		if (A[i] != B[i]) {
			ans += N - i;
			break;
		}
		else if (A[i] == '1') ans++;
	}
	cout << ans;
}

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

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

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

두 수 모두 0으로 시작하지 않고 두 수는 서로 다르므로, (1)길이가 다르면 더 긴 수가 항상 더 크고 (2) 길이가 같다면 첫 문자부터 비교해나가면서 처음으로 서로 다른 문자가 나왔을 때의 그 두 문자 중 더 큰 수를 나타내는 쪽이 더 큰 수가 됨을 관찰하자.

한편 아스키코드에서는 (숫자) < (대문자) < (소문자) 순으로 코드가 할당되어 있으므로, 각 대문자와 소문자를 뒤바꿔주면 위의 (2) 과정은 단순 문자열비교로 판단 가능하게 된다.

위의 관찰을 이용해 문제를 해결하자.

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

int T;
string A, B;

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

	cin >> T;
	while (T--) {
		cin >> A >> B;
		if (A > B) swap(A, B);
		for (auto &l:A) {
			if ('a' <= l && l <= 'z') l = toupper(l);
			else if ('A' <= l && l <= 'Z') l = tolower(l);
		}
		for (auto &l:B) {
			if ('a' <= l && l <= 'z') l = toupper(l);
			else if ('A' <= l && l <= 'Z') l = tolower(l);
		}
		
		if (A.length() > B.length()) cout << "NO\n";
		else if (A.length() < B.length()) cout << "YES\n";
		else {
			bool chk = 1; int alen = A.length();
			for (int i = 0; i < alen; i++) {
				if (A[i] > B[i]) {
					chk = 0;
					break;
				}
				else if (A[i] < B[i]) break;
			}
			if (chk) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}