취미로 코딩하기

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

이번에 볼 문제는 백준 33163번 문제인 OIJ (OIJ)이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열의 각 'J'는 'O'로, 각 'O'는 'I'로, 각 'I'는 'J'로 바꾸어 출력하는 문제이다.

글쓴이는 각 문자마다 해당 문자가 바뀌게 되는 문자를 기록해 둔 배열을 만들어 문제를 해결하였다.

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

#include <iostream>
using namespace std;

int N;
char A[128];

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

    A['J'] = 'O', A['O'] = 'I', A['I'] = 'J';
    cin >> N;
    while (N--) {
        char c; cin >> c;
        cout << A[c];
    }
}

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

이번에 볼 문제는 백준 33162번 문제인 散歩 (Walking)이다.
문제는 아래 링크를 확인하자.

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

JOI군은 홀수번째 이동에서는 3미터 앞으로 이동하며 짝수번째 이동에서는 2미터 뒤로 이동함을 관찰하자.

따라서 \(X\)까지의 홀수의 개수만큼 3미터 앞으로 이동 및 짝수의 개수만큼 2미터 뒤로 이동했을 때의 출발점으로부터의 변위가 문제의 답이 된다.

\(X\)의 제한이 작으므로 그냥 반복문을 통해 이동을 시뮬레이션하는 것으로 답을 구해도 좋다.

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

#include <iostream>
using namespace std;

int N, A, B;

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

    cin >> N;
    B = N / 2, A = N - B;
    cout << A * 3 - B * 2;
}

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

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