취미로 코딩하기

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

이번에 볼 문제는 백준 33135번 문제인 鉛筆 2 (Pencils 2)이다.
문제는 아래 링크를 확인하자.

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

\(N\)엔(円)으로 살 수 있는 5엔짜리 연필의 개수는 \(N\)을 5로 나눈 몫과 같다. 이를 구현하여 문제를 해결하자.

C++에서 '/' 연산자를 이용하면 정수의 나눗셈의 몫을 구할 수 있다.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	cout << N / 5;
}

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

이번에 볼 문제는 백준 33135번 문제인 Append and Panic!이다.
문제는 아래 링크를 확인하자.

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

새로 추가된 문자의 개수는 기존에 있던 문자열에 있던 문자의 가짓수와 같으며, 새로 추가된 문자는 기존에 있던 문자의 집합과 같으므로 바뀐 문자열에 포함된 문자의 가짓수는 기존에 있던 문자열의 문자의 가짓수와 같다는 점을 관찰하자.

따라서 주어진 문자열의 서로 다른 문자의 개수를 세어 문자열의 길이에서 그 값을 빼는 것으로 문제를 해결할 수 있다.

표준 라이브러리의 std::string을 이용하여 구현을 편하게 하자.

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

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

int ans;
string s;
bool visited[128];

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

    cin >> s; ans = s.length();
    for (auto &l:s) {
        if (visited[l]) continue;
        visited[l] = 1, ans--;
    }

    cout << ans;
}

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

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

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

주어진 그래프는 정점이 \(N\)개이며 에지 또한 \(N\)개(중복 포함)임을 관찰할 수 있다.

따라서 주어진 그래프를 직접 인접리스트 등의 자료구조로 표현한 다음 그래프 탐색을 통해 주어진 그래프가 connected인지를 확인하는 것으로 문제를 해결할 수 있다. DFS나 BFS 등 편한 방법을 선택해 구현하자.

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

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

int N;
vector<int> G[1000001];
bool visited[1000001];

void dfs(int cur) {
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int j = (i * 3 + 7) % N;
		G[i].emplace_back(j);
		G[j].emplace_back(i);
	}
	dfs(0);
	for (int i = 1; i < N; i++) {
		if (!visited[i]) {
			cout << "NO\n" << 0 << ' ' << i;
			return 0;
		}
	}
	cout << "YES";
}

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

이번에 볼 문제는 백준 32925번 문제인 Just Half is Enough이다.
문제는 아래 링크를 확인하자.

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

일단 정점을 아무 순서로나 나열해보자. 이 때 각 에지는 앞서 나열한 것을 기준으로 조건에 맞게 나열되었거나 그렇지 않은 둘 중 하나의 상태가 된다.

한편, 위의 나열의 순서를 뒤집으면 앞서 조건에 맞게 나열되었던 에지는 조건에 맞지 않게 될 것이며 그렇지 않은 에지는 조건에 맞게 될 것임을 관찰할 수 있다.

따라서, 위 관찰로부터 어떤 나열에 대하여 해당 나열과 이를 뒤집은 나열 둘 중 하나는 항상 조건을 만족함을 알 수 있다. 이를 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, M, cnt;

void solve() {
	cnt = 0;
	cin >> N >> M;
	for (int m = 0; m < M; m++) {
		int x, y; cin >> x >> y;
		if (x < y) cnt++;
	}
	if (M - cnt <= cnt) {
		for (int i = 1; i <= N; i++) cout << i << ' ';
	}
	else {
		for (int i = N; i > 0; i--) cout << i << ' ';
	}
	cout << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}

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

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

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

어떤 항에서부터 수열을 보기 시작하더라도 \(N\)개 항씩 건너뛰면서 읽으면 공차가 주어지는 \(D_i\)의 합으로 일정한 등차수열이 됨을 관찰하자.

따라서 첫 \(N\)개의 항에 대하여 얻을 수 있는 각 등차수열에 대하여 \(X\) 이상의 값이 해당 등차수열에 있는지, 있다면 그러한 값의 최솟값을 구해 문제의 답을 구할 수 있다.

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

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

ll N, val, X, gap;
ll D[100000];
ll ans = 1000000000000000007LL;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> val >> X;
	for (int i = 0; i < N; i++) cin >> D[i], gap -= D[i];
	for (int i = 0; i < N; i++) {
		if (val >= X) ans = min(ans, val - (val - X) / gap * gap);
		val += D[i];
	}

	if (ans < 1000000000000000007LL) cout << ans;
	else cout << -1;
}

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

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

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

어떤 수가 선택된 세 수의 중앙값이 되려면 그 수보다 작거나 같은 수가 선택된 세 수에 포함(자기자신 제외)되어 있어야 함을 관찰하자. 따라서 주어진 \(3N\)개의 수 중 \(N+2\)번째 수가 가장 작은 중앙값이 되게 하는 방법은 없지만 \(N+1\)번째 수가 가장 작은 중앙값이 되게 하는 방법은 존재함(예를 들어 \(i\)번째, \(i+N\)번째, \(i+2N\)번째 수와 같이 모든 쌍을 구성)을 알 수 있다.

따라서 주어진 수 중 \(N+1\)번째로 작은 수를 출력해 문제를 해결할 수 있다. 이는 자료를 정렬한 뒤 해당 순서의 자료를 고르는 것으로 간편하게 할 수 있다. 원한다면 퀵셀렉트 등의 다른 알고리즘을 사용해도 좋다.

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

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

int N;
int A[300000];

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

	cin >> N;
	for (int i = 0; i < N * 3; i++) cin >> A[i];
	sort(A, A + N * 3);
	cout << A[N];
}