취미로 코딩하기

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

이번에 볼 문제는 백준 16928번 문제인 뱀과 사다리 게임이다.
문제는 아래 링크를 확인하자.

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

뱀과 사다리 게임판을 하나의 그래프로 생각해보자.

게임판의 각 칸을 하나의 노드로 생각하고, 각 칸 A에서 주사위를 던져서 (사다리와 뱀 등을 거친 후) 이동하게 되는 칸 B로 이동하는 것을 하나의 에지로 생각할 수 있다.

이 때, 이 문제를 푸는 것은 에지를 최소 몇개를 거쳐서 1에서 100까지 이동할 수 있는가가 된다. 이는 BFS를 이용하여 간단히 해결할 수 있다.

99번 칸에서 6의 주사위눈이 나온다던가 하는 100번칸을 넘어가는 이동이 없다는 점에 신경을 써서 구현하자.

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

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

int board[106];
int dist[106];

queue<int> que;
bool visited[106];

void bfs() {
	while (!que.empty()) {
		int current = que.front(); que.pop();
		for (int i = 1; i <= 6; i++) {
			int next = board[current + i];
			if (visited[next]) continue;
			visited[next] = 1;
			dist[next] = dist[current] + 1;
			que.push(next);
		}
	}
}

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

	for (int i = 1; i <= 100; i++) board[i] = i;

	int N, M; cin >> N >> M;
	N += M;

	while (N--) {
		int x, y; cin >> x >> y;
		board[x] = y;
	}

	visited[1] = 1;
	que.push(1);
	bfs();

	cout << dist[100];
}

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

이번에 볼 문제는 백준 12852번 문제인 1로 만들기 2이다.
문제는 아래 링크를 확인하자.

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

1부터 100만까지의 수 i를 둘러보면서 1로 만드는 과정 중 이 숫자 이전에 올 수 있었을 수(i*3, i*2, i+1)들의 차례를 한 번씩 확인해주는 것으로 문제를 해결할 수 있다. (또는 각 숫자를 노드로 생각하여 BFS를 사용할 수도 있다.)

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

#include <iostream>
using namespace std;

int dp[1000001];
int backtrack[1000001];

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

	dp[1] = 1;

	for (int i = 1; i < 1000000; i++) {
		if (i * 3 < 1000000) {
			if (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1) {
				dp[i * 3] = dp[i] + 1;
				backtrack[i * 3] = i;
			}
		}
		if (i * 2 <= 1000000) {
			if (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1) {
				dp[i * 2] = dp[i] + 1;
				backtrack[i * 2] = i;
			}
		}
		if (i < 1000000) {
			if (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1) {
				dp[i + 1] = dp[i] + 1;
				backtrack[i + 1] = i;
			}
		}
	}

	int N; cin >> N;
	cout << dp[N] - 1 << '\n';
	while (N != 1) {
		cout << N << ' ';
		N = backtrack[N];
	}
	cout << 1;
}

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

이번에 볼 문제는 백준 20305번 문제인 피보나치와 수열과 쿼리이다.
문제는 아래 링크를 확인하자.

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

이 문제를 풀기 위해 관찰해야할 것은 다음 두 가지이다.

1) 모든 쿼리를 처리한 이후의 최종 결과만을 출력하면 된다. 또한, 이 문제에서 주어지는 쿼리는 순서를 바꿔서 계산해도 최종 결과가 변하지 않는다. (단순한 덧셈이므로)

2) 피보나치 수의 특징을 생각하여, 각 쿼리를 입력받아 시작점, 끝점에 1과 쿼리 구간길이에 대응되는 적절한 피보나치수를 구간의 끝에서 빼주는 것으로 미리 전부 업데이트를 하고 피보나치 점화관계를 이용하여 수열을 구해낼 수 있다.

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

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

ll fib[1000011];
ll arr[1000011];

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

    fib[1] = fib[2] = 1;
    int N, Q; cin >> N >> Q;
    
    for (int i = 3; i <= 1000010; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2])%1000000007;
    }

    while (Q--) {
        int x, y; cin >> x >> y;
        arr[x] += 1;
        arr[y + 1] -= fib[y - x + 2];
        arr[y + 2] -= fib[y - x + 1];
    }
    
    for (int i = 1; i <= N; i++) {
        cout << arr[i] << ' ';
        arr[i + 1] += arr[i-1] + arr[i];
        arr[i + 1] %= 1000000007;
        if (arr[i + 1] < 0) arr[i + 1] += 1000000007;
    }
}

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

이번에 볼 문제는 백준 16953번 문제인 A → B이다.
문제는 아래 링크를 확인하자.

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

주어진 정수의 끝에 1을 붙이는 것은 주어진 정수에 10을 곱하고 1을 더한 것과 같다는 점을 떠올린다면, 수에 가할 수 있는 조작 두 가지 모두 수가 지수적으로 증가하므로 bfs를 통해 시간 내로 문제를 간단히 해결할 수 있다.

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

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

ll E;
queue<pair<ll, int>> que;

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

	ll temp; cin >> temp >> E;
	que.push({ temp,1 });

	while (!que.empty()) {
		ll current = que.front().first;
		int idx = que.front().second;
		que.pop();

		if (current == E) {
			cout << idx;
			return 0;
		}

		if (2 * current <= 1000000000) que.push({ 2 * current,idx + 1 });
		if (10 * current + 1 <= 1000000000) que.push({ 10 * current + 1,idx + 1 });
	}

	cout << -1;
}

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

이번에 볼 문제는 백준 5397번 문제인 키로거이다.
문제는 아래 링크를 확인하자.

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

현재 빵의 상태에서 목표로 하는 빵의 상태로 만들기까지 "인접한 빵끼리 swap"을 이용하여 만들 때 필요한 횟수와 "빵 던지기 기술을 이용한 자리바꾸기"를 이용할 때 "인접한 빵끼리 swap"을 몇 번한 것과 같은지를 생각해보자.

위의 생각을 통해 규칙을 찾았다면, inversion counting을 통해 문제를 간단히 해결할 수 있다.

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

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

int idx[100001];
int seg[262145];

void update(int L, int R, int qI) {
	int sI = 1;
	while (L < R) {
		seg[sI]++;
		int mid = (L + R) / 2;
		if (qI <= mid) {
			R = mid; sI = sI * 2;
		}
		else {
			L = mid + 1; sI = sI * 2 + 1;
		}
	}
	seg[sI]++;
}

int query(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

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

	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		idx[x] = i;
	}

	ll cnt = 0;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		x = idx[x];
		cnt += (ll)query(1, N, x, N, 1);
		update(1, N, x);
	}

	if (cnt & 1) cout << "Impossible";
	else cout << "Possible";
}

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

이번에 볼 문제는 백준 5002번 문제인 도어맨이다.
문제는 아래 링크를 확인하자.

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

맨 앞의 한 사람을 건너뛰고 손님들을 받을 수 있다는 조건을 잘 처리해야하는 문제이다.

건너뛴 손님을 저장할 변수와 남녀 수의 차이를 저장할 변수를 하나 만들고, 남녀 수의 차이가 도어맨이 기억하지 못하는 범위에 도달할 때마다 건너뛴 손님이 있었는지, 있었다면 지금 이 손님을 입장시켜도 되는지 등을 신경써 구현하면 해결할 수 있는 문제이다.

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

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

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

	int X; cin >> X;
	string s; cin >> s;

	int diff = 0;
	char save = ' ';

	int ans = 0;
	for (auto c : s) {
		if (c == 'M') {
			if (diff != X) diff++;
			else {
				if (save == 'M') break;
				else if (save == ' ') save = 'M';
				else {
					save = ' ';
				}
			}
		}
		else { // c == 'W'
			if (diff != -X) diff--;
			else {
				if (save == 'W') break;
				else if (save == ' ') save = 'W';
				else {
					save = ' ';
				}
			}
		}
		ans++;
	}

	if (save == ' ') cout << ans;
	else if (save == 'M') {
		if (diff == X) cout << ans - 1;
		else cout << ans;
	}
	else { // save == 'W'
		if (diff == -X) cout << ans - 1;
		else cout << ans;
	}
}