취미로 코딩하기

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

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

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

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