취미로 코딩하기

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

이번에 볼 문제는 백준 11062번 문제인 카드 게임이다.
문제는 아래 링크를 확인하자.

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

dp[i][j] := i번 카드부터 j번 카드까지의 범위의 카드들로 게임을 할 때 근우가 얻게 될 점수

위와 같은 dp식을 세우고, i와 j의 차를 0부터 N-1까지 키워나가면서 dp[0][N-1]을 구하는 것으로 문제를 풀 수 있다.

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

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

int arr[1000];
int dp[1000][1000];

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

	int T; cin >> T;
	while (T--) {
		memset(dp, 0, sizeof(dp));
		int N; cin >> N;
		for (int i = 0; i < N; i++) cin >> arr[i];
		if (N & 1) {
			for (int d = 0; d < N; d++) {
				for (int i = d; i < N; i++) {
					if (d & 1) dp[i - d][i] = min(dp[i - d][i - 1], dp[i - d + 1][i]);
					else dp[i - d][i] = max(dp[i - d][i - 1] + arr[i], arr[i - d] + dp[i - d + 1][i]);
				}
			}
		}
		else {
			for (int d = 0; d < N; d++) {
				for (int i = d; i < N; i++) {
					if (!(d & 1)) dp[i - d][i] = min(dp[i - d][i - 1], dp[i - d + 1][i]);
					else dp[i - d][i] = max(dp[i - d][i - 1] + arr[i], arr[i - d] + dp[i - d + 1][i]);
				}
			}
		}

		cout << dp[0][N - 1] << '\n';
	}
}

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

이번에 볼 문제는 백준 2468번 문제인 안전 영역이다.
문제는 아래 링크를 확인하자.

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

잘 생각해보면, 높이가 1보다 큰 지점들과 그런 지점들을 잇는 에지만으로 이루어진 그래프의 component의 개수의 최댓값을 구하는 문제이다. N과 지점의 높이의 크기제한이 작으므로, 각 높이제한에 대하여 component의 개수를 각각 세어보는 것으로 문제를 해결할 수 있다.

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

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

short arr[100][100];
int visited[100][100];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

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

	int N; cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> arr[r][c];
	}

	int ans = 1;
	for (int h = 2; h <= 100; h++) {
		int cnt = 0;
		memset(visited, 0, sizeof(visited));
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (visited[r][c]) continue;
				if (arr[r][c] < h) {
					visited[r][c] = 1;
					continue;
				}
				cnt++;
				visited[r][c] = 1;
				queue<pair<int, int>> que; que.push({ r,c });
				while (!que.empty()) {
					int curr = que.front().first, curc = que.front().second; que.pop();
					for (int i = 0; i < 4; i++) {
						int rr = curr + dr[i], cc = curc + dc[i];
						if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
						if (visited[rr][cc]) continue;
						visited[rr][cc] = 1;
						if (arr[rr][cc] < h) continue;
						que.push({ rr,cc });
					}
				}
			}
		}
		ans = max(ans, cnt);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 16434번 문제인 드래곤 앤 던전이다.
문제는 아래 링크를 확인하자.

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

던전을 진행하면서, 최대 얼마까지 체력이 깎일 수 있는지를 시뮬레이션을 통해 구하는 것으로 문제를 해결할 수 있다.

몬스터와의 전투를 단순히 반복문으로 구현한다면 TLE가 나올 수 있으니 주의하자.

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

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

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

    int N; cin >> N;
    ll curHP = 0, ATK; cin >> ATK;
    ll ans = 0;
    while (N--) {
        ll t, a, h; cin >> t >> a >> h;
        if (t == 1) {
            h -= ATK;
            if (h > 0) {
                if (h % ATK == 0) curHP += a * h / ATK;
                else curHP += a * (h / ATK + 1);
            }
        }
        else {
            curHP = max(curHP - h, 0LL);
            ATK += a;
        }
        ans = max(ans, curHP);
    }

    cout << ans + 1;
}

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

이번에 볼 문제는 백준 2565번 문제인 전깃줄이다.
문제는 아래 링크를 확인하자.

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

서로 교차하지 않는 전깃줄의 최대 개수는 한쪽 전봇대를 기준으로 1번서부터 연결된 전깃줄의 끝의 LIS와 같다는 점을 확인하자.

글쓴이는 LIS를 세그먼트 트리를 이용하여 구했다.

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

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

int seg[1025];

int update(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = qVal;
	return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int rangemax(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 max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

vector<pair<int, int>> queries;

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		queries.push_back({ x,y });
	}
	sort(queries.begin(), queries.end());

	for (auto q : queries) {
		int lis = rangemax(1, 500, 1, q.second, 1) + 1;
		update(1, 500, q.second, lis, 1);
	}

	cout << N - seg[1];
}

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

이번에 볼 문제는 백준 5557번 문제인 1학년이다.
문제는 아래 링크를 확인하자.

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

2차원 배열을 만들어, 이전 숫자까지 계산을 마쳤을 때 0~20의 숫자들이 각각 만들어질 수 있는 경우의 수를 관리해주자.

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

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

ll arr[100][21];

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

	int N; cin >> N;
	int x; cin >> x;
	arr[1][x] = 1;
	for (int i = 2; i < N; i++) {
		cin >> x;
		for (int j = 0; j <= 20; j++) {
			if (0 <= j - x) arr[i][j - x] += arr[i - 1][j];
			if (j + x <= 20) arr[i][j + x] += arr[i - 1][j];
		}
	}

	cin >> x;
	cout << arr[N - 1][x];
}

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

이번에 볼 문제는 백준 3835번 문제인 Alphabet Soup이다.
문제는 아래 링크를 확인하자.

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

원형으로 알파벳을 놓을 수 있는 각도들이 정해져있을 때 얼마나 다양하게 알파벳을 배치할 수 있는가를 묻는 문제이다.

먼저 수프를 회전했을 때 처음과 같은 각도들의 배치가 나오게 하는 최소 각도를 구하자. 이는 KMP 알고리즘의 fail함수를 활용해 구해줄 수 있다.

그 다음으로 그만큼의 각도에 놓을 수 있는 총 알파벳의 개수를 이용해 존재할 수 있는 구간의 경우의 수를 구하고, 그러한 구간을 원모양으로 배치하는 경우의 수를 번사이드 보조정리를 이용하여 구하는 것으로 문제를 해결할 수 있다.

1,000,000,007로 나눈 나머지를 구하는 것이 아닌 100,000,007로 나눈 나머지를 구하는 문제임에 유의하자.

또한, 수프를 뒤집어엎으면 안된다는 점에 유의하자.

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

#define MOD 100000007
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int arr[360000];
int pi[360000];

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

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

	ll N, M; cin >> N >> M;
	while (N >= 0) {
		memset(arr, 0, sizeof(arr));
		memset(pi, 0, sizeof(pi));
		for (int m = 0; m < M; m++) {
			int x; cin >> x;
			arr[x] = 1;
		}

		for (int i = 0; i < 360000; i++) {
			int idx = i;
			while (idx > 0) {
				if (arr[pi[idx - 1]] == arr[i]) break;
				idx = pi[idx - 1];
			}
			if (idx == 0) pi[i] = 0;
			else pi[i] = pi[idx - 1] + 1;
		}
		ll L = 360000 - pi[359999];
		if (360000 % L != 0) L = 360000;
		ll beads = 360000 / L;

		ll colors = 1;
		for (int l = 0; l < L; l++) {
			if (arr[l]) colors = (colors * N) % MOD;
		}

		ll total = 0;
		for (ll i = 1; i <= beads; i++) {
			ll cur = gcd(i, beads);
			ll ret = 1;
			ll CC = colors;
			while (cur > 0) {
				if (cur & 1) ret = (ret * CC) % MOD;
				CC = (CC * CC) % MOD;
				cur >>= 1;
			}
			total = (total + ret) % MOD;
		}

		ll invbeads = 1;
		int p = 100000005;
		while (p > 0) {
			if (p & 1) invbeads = (beads * invbeads) % MOD;
			beads = (beads * beads) % MOD;
			p >>= 1;
		}

		cout << (total * invbeads) % MOD << '\n';
		cin >> N >> M;
	}
}