취미로 코딩하기

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

이번에 볼 문제는 백준 32963번 문제인 맛있는 사과이다.
문제는 아래 링크를 확인하자.

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

먼저 사과의 나열 순서와 답은 상관관계가 없으므로 주어진 사과를 크기순으로 정렬해도 답이 변하지 않음을 관찰하자. 그리고 사과를 크기순으로 정렬하자.

다음으로, 큰 사과부터 차례대로 보면서 가장 큰 사과의 크기가 얼마인지, 그 크기의 사과가 몇개인지를 두 변수를 활용해 관리하고, 크기 역순으로 해당 사과까지 확인했을 때의 문제의 답이 무엇인지를 잘 기록해두자.

이제 각 쿼리로 주어진 수에 대하여 해당 수보다 크거나 같은 사과 중 가장 인덱스가 작은 사과부터 마지막 사과까지의 사과 중 가장 큰 사과의 개수가 몇 개인지 앞서 구한 배열을 이용해 답하는 것으로 문제를 해결할 수 있다. 이러한 인덱스는 이진 탐색으로 구할 수 있다.

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

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

int N, Q, mx = -1, cnt = 0;
pair<int, int> P[200000];

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

    cin >> N >> Q;
    for (int i = 0; i < N; i++) cin >> P[i].first;
    for (int i = 0; i < N; i++) cin >> P[i].second;

    sort(P, P + N);
    for (int i = N - 1; i > -1; i--) {
        if (P[i].second > mx) mx = P[i].second, cnt = 1;
        else if (P[i].second == mx) cnt++;
        P[i].second = cnt;
    }

    while (Q--) {
        int K, L = 0, R = N - 1; cin >> K;
        if (P[N - 1].first < K) cout << 0 << '\n';
        else {
            while (L < R) {
                int mid = (L + R) / 2;
                if (P[mid].first < K) L = mid + 1;
                else R = mid;
            }
            cout << P[L].second << '\n';
        }
    }
}

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

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

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

문제에 주어진 대로, 먼저 주어지는 수 중 가장 큰 값과 작은 값을 구하자. 그리고 큰 값의 절반에서 작은 값을 뺀 값이 양수이면 그 값이, 양수가 아니라면 0이 문제의 답이 된다.

조건에 따라 입력으로 주어지는 \(P\) 값은 모두 10의 배수이므로 2로 나눈 값이 소수가 되는 경우는 입력으로 주어지지 않음을 확인하자. 따라서 별다른 걱정 없이 정수로 모든 구현을 마쳐도 된다.

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

#include <iostream>
using namespace std;

int N, mn = 1000000007, mx = -1000000007;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		mn = min(mn, x);
		mx = max(mx, x);
	}

	cout << max(mn - mx / 2, 0);
}

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

이번에 볼 문제는 백준 32936번 문제인 타임머신이다.
문제는 아래 링크를 확인하자.

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

답이 "-inf"가 되려면 일단 (1) 1번 정점에서 타임머신을 이용하러 갈 수 있으며 (2) 타임머신 이용 후 다시 타임머신을 이용하러 갈 수 있고 (3) 2의 과정에 드는 시간이 타임머신으로 되돌아가는 시간보다 적으며 (4) 타임머신 이용 후 \(N\)번 정점으로 이동할 수 있어야 한다.

위의 내용이 성립하지 않으면 일단 답은 "-inf'가 아니다. 이 때 가능한 답의 후보는 (1)1번 정점에서 타임머신을 이용하지 않고 \(N\)번 정점으로 가는 것과 (2) 1번 정점에서 타임머신을 한 번 이용하고 \(N\)번 정점으로 가는 것이다. 타임머신을 2번 이상 사용하는 것이 1번 사용한 것보다 더 거리가 짧다면 타임머신을 더 많이 사용하는 것이 이득이 됨을 관찰하자.

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

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

int N, M, A, B, C;
vector<int> G[200001];
queue<int> que;
int dist[200001];
int dd = 1000000007, da = 1000000007, db = 1000000007, dba = 1000000007;

void bfs(int S) {
	memset(dist, 0, sizeof(dist));
	dist[S] = 1;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto &nxt:G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

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

	cin >> N >> M >> A >> B >> C;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
	}

	bfs(1);
	if (dist[N]) dd = dist[N] - 1;
	if (dist[A]) da = dist[A] - 1;
	bfs(B);
	if (dist[N]) db = dist[N] - 1;
	if (dist[A]) dba = dist[A] - 1;

	if (da < 1000000007 && db < 1000000007) dd = min(dd, da + db - C);
	if (da < 1000000007 && db < 1000000007 && dba < 1000000007 && dba < C) cout << "-inf";
	else if (dd < 1000000007) cout << dd;
	else cout << 'x';
}

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

이번에 볼 문제는 백준 32908번 문제인 Programmers and Stones이다.
문제는 아래 링크를 확인하자.

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

자신의 차례에 홀수개의 돌이 포함된 돌무더기가 존재한다면 그러한 돌무더기에서 돌을 하나씩 제거하고 나머지 돌무더기에서는 돌을 제거하지 않아 모든 돌무더기에 각각 짝수개(0 포함)의 돌이 포함되게 만들 수 있다. 그리고 자신의 차례에 홀수개의 돌이 포함된 돌무더기가 존재하지 않는다면 남은 돌이 없거나 자신의 차례 후에 항상 홀수개의 돌이 포함된 돌무더기가 생기게 된다.

위의 관찰을 이용하면 초기 상태에 홀수개의 돌이 포함된 돌무더기의 존재 여부로 게임을 이기는 사람이 결정된다는 점을 관찰할 수 있다.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x & 1) {
			cout << "Alice";
			return 0;
		}
	}
	cout << "Dmitry";
}

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

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

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

어떤 수 $n$를 나타내는 문자열 $s$가 있을 때, $s$의 문자를 순서대로 살펴보면서 초기값 0에 {가 등장하면 1을 더하고 }가 등장하면 -1을 더해나가면서 얻을 수 있는 중간결괏값의 최댓값을 구하자. 이 값은 $n+1$과 같게 된다. 증명은 수학적 귀납법으로 어렵지 않게 할 수 있다. 

따라서 위의 관찰을 이용해 $n$을 계산하는 것으로 문제를 해결할 수 있다.

다른 풀이 방법으로, 각 수를 나타내는 문자열 $s$의 길이값의 규칙을 찾아 문제를 해결할 수도 있다.

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

#include <iostream>
using namespace std;

char c;
int mx, val;

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

	while (cin >> c) {
		if (c == '{') val++;
		else if (c == '}') val--;
		mx = max(mx, val);
	}
	cout << mx - 1;
}

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

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