취미로 코딩하기

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

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

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

$k$번째 wonowon 수를 $w_k$라 할 때, $k+1$번째 wonowon 수는 $100w_k+1$로 계산할 수 있음을 관찰하자.

이를 이용해 (2, 3 및 5를 제외한) $N$ 이하의 소수 $p$에 대하여 $W(p)$를 각각 직접 계산해 조건을 만족하는 소수의 개수를 세는 것으로 문제를 해결할 수 있다. 이 과정에서 wonowon 수를 1010101...의 형태로 모든 자릿수를 보관하는 대신 각 소수 $p$로 나눈 나머지의 형태로 보관해 오버플로우를 피하자.

각 수가 소수인지는 에라토스테네스의 체를 이용해 미리 전처리해두는 것으로 판별할 수 있다. 이 문제에서는 입력의 크기가 충분히 작으므로 $p$가 소수인지 판단하기 위해 $\sqrt{p}$까지의 각 양의 정수로 직접 나눠봐도 무방하다.

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

#include <iostream>
using namespace std;

int ans;
int cur = 1, cnt = 1;

bool sieve[10001];

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

	for (int i = 2; i < 100; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 10001; j += i) sieve[j] = 1;
	}

	int N; cin >> N;
	for (int p = 7; p <= N; p++) {
		if (sieve[p]) continue;
		cur = 1, cnt = 1;
		while (cur) cur = (cur * 100 + 1) % p, cnt += 2;
		if (cnt == p - 2) ans++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 11287번 문제인 Margaret’s Minute Minute Manipulation이다.
문제는 아래 링크를 확인하자.

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

주어지는 표 형태의 시간으로부터, 표의 각 열을 이진수를 십진수로 변환하는 것으로 HH:MM:SS의 각 자리를 구할 수 있다. HH:MM:SS 형태의 시간을 다시 초단위로 바꿔 저장해 문제에서 요구하는 시각 T+δ를 찾아내고, 이를 주어지는 표 형태로 다시 돌려놓는 것으로 문제를 해결하자.

올바른 시간 표기는 00:00:00부터 23:59:59까지임에 유의하자.

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

#include <iostream>
using namespace std;

int T, D, TD;
int H, M, S;
int table[4][6];

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

	for (int r = 0; r < 4; r++) {
		for (int c = 0; c < 6; c++) {
			cin >> table[r][c];
		}
	}
	T += (table[0][0] * 8 + table[1][0] * 4 + table[2][0] * 2 + table[3][0]) * 36000;
	T += (table[0][1] * 8 + table[1][1] * 4 + table[2][1] * 2 + table[3][1]) * 3600;
	T += (table[0][2] * 8 + table[1][2] * 4 + table[2][2] * 2 + table[3][2]) * 600;
	T += (table[0][3] * 8 + table[1][3] * 4 + table[2][3] * 2 + table[3][3]) * 60;
	T += (table[0][4] * 8 + table[1][4] * 4 + table[2][4] * 2 + table[3][4]) * 10;
	T += (table[0][5] * 8 + table[1][5] * 4 + table[2][5] * 2 + table[3][5]) * 1;

	for (int r = 0; r < 4; r++) {
		for (int c = 0; c < 6; c++) {
			cin >> table[r][c];
		}
	}
	D += (table[0][0] * 8 + table[1][0] * 4 + table[2][0] * 2 + table[3][0]) * 36000;
	D += (table[0][1] * 8 + table[1][1] * 4 + table[2][1] * 2 + table[3][1]) * 3600;
	D += (table[0][2] * 8 + table[1][2] * 4 + table[2][2] * 2 + table[3][2]) * 600;
	D += (table[0][3] * 8 + table[1][3] * 4 + table[2][3] * 2 + table[3][3]) * 60;
	D += (table[0][4] * 8 + table[1][4] * 4 + table[2][4] * 2 + table[3][4]) * 10;
	D += (table[0][5] * 8 + table[1][5] * 4 + table[2][5] * 2 + table[3][5]) * 1;

	TD = T + D;
	if (TD >= 86400) TD -= 86400;

	H = TD / 3600; TD %= 3600;
	M = TD / 60; TD %= 60;
	S = TD;

	int cur = H / 10; H %= 10;
	for (int i = 3; i > -1; i--) {
		table[i][0] = cur & 1;
		cur >>= 1;
	}
	cur = H;
	for (int i = 3; i > -1; i--) {
		table[i][1] = cur & 1;
		cur >>= 1;
	}
	cur = M / 10; M %= 10;
	for (int i = 3; i > -1; i--) {
		table[i][2] = cur & 1;
		cur >>= 1;
	}
	cur = M;
	for (int i = 3; i > -1; i--) {
		table[i][3] = cur & 1;
		cur >>= 1;
	}
	cur = S / 10; S %= 10;
	for (int i = 3; i > -1; i--) {
		table[i][4] = cur & 1;
		cur >>= 1;
	}
	cur = S;
	for (int i = 3; i > -1; i--) {
		table[i][5] = cur & 1;
		cur >>= 1;
	}

	for (int r = 0; r < 4; r++) {
		for (int c = 0; c < 6; c++) {
			cout << table[r][c] << ' ';
		}
		cout << '\n';
	}
}

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

이번에 볼 문제는 백준 11288번 문제인 Ether's Encryption이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열의 각 대문자들을(즉, ' '를 제외한 모든 문자들을) $a^b$만큼 shift시키는 것으로 문제를 해결하자.

이 shift연산은 26을 주기로 반복되므로 $a^b$ 대신 $a^b$을 계산하는 것으로도 문제를 충분히 해결할 수 있다. 이 값은 $a$ 대신 $a$을 이용하고 $a$를 반복해 곱해나가는 과정에서도 그 결과를 26으로 나눈 나머지를 저장하는 것으로 계산해낼 수 있다.

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

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

int slen; ll a, b, d = 1;
string s;

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

	cin >> slen >> a >> b;
	a %= 26;
	for (int k = 0; k < b; k++) {
		d = (d * a) % 26;
	}

	getline(cin, s);
	getline(cin, s);
	for (auto& l : s) {
		if (l == ' ') cout << ' ';
		else {
			char nxt = l - d;
			if (nxt < 'A') nxt += 26;
			cout << nxt;
		}
	}
}

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

이번에 볼 문제는 백준 11289번 문제인 Boolean Postfix이다.
문제는 아래 링크를 확인하자.

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

bool 변수의 and, or, xor 및 not 연산을 지원하는 후위표기식의 계산을 구현하는 문제이다.

후위표기식의 계산은 스택 자료구조를 이용하면 아래와 같이 편하게 구현할 수 있다.

C++에서 and는 '&', or은 '|', xor은 '^'으로 표현한다는 점을 상기해 문제를 해결하자.

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

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

int T;
stack<bool> stk;

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

	cin >> T;
	while (T--) {
		int N; cin >> N;
		while (N--) {
			char c; cin >> c;
			if (c == '0') stk.push(0);
			else if (c == '1') stk.push(1);
			else if (c == 'A') {
				bool x = stk.top(); stk.pop();
				bool y = stk.top(); stk.pop();
				stk.push(x & y);
			}
			else if (c == 'R') {
				bool x = stk.top(); stk.pop();
				bool y = stk.top(); stk.pop();
				stk.push(x | y);
			}
			else if (c == 'X') {
				bool x = stk.top(); stk.pop();
				bool y = stk.top(); stk.pop();
				stk.push(x ^ y);
			}
			else {
				bool x = stk.top(); stk.pop();
				stk.push(x ^ 1);
			}
		}

		bool x = stk.top(); stk.pop();
		cout << x << '\n';
	}
}

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

이번에 볼 문제는 백준 11291번 문제인 Alicia's Afternoon Amble이다.
문제는 아래 링크를 확인하자.

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

각 장소에 x좌표 오름차순으로 0부터 N-1까지의 index를 부여하자.

그리고 $dp[i][j]$ (단, $i<j$)를 "장소 0부터 장소 i까지 가는, 경유하는 장소의 x좌표가 오름차순인 경로 $P1$과 장소 0부터 장소 j까지 가는, 경유하는 장소의 x좌표가 오름차순인 경로 $P2$가 있을 때 아래의 조건을 만족하는 두 경로에 대하여 그 경로의 길이의 합의 최솟값으로 정의하자.

$P1$을 구성하는 장소와 $P2$를 구성하는 장소는 장소 0을 제외하고 서로 다르면서 둘을 구성하는 장소의 합집합은 j 이하의 장소를 모두 포함하고 있어야 한다.

이 때 $i$와 $j$의 차가 2 이상이라면 $dp[i][j]=dp[i][j-1]+dist(j-1,j)$ 와 같이 계산할 수 있음을 알 수 있다. 

$i+1=j$이면 $dp[i][j]=min(dp[k][j-1]+dist(k,j))$ (단, $k<j-1$)와 같이 계산할 수 있다.

또한 문제의 답은 $min(dp[k][N-1]+dist(k,N-1))$ (단, $k<N-1$)와 같이 계산할 수 있다.

위의 점화관계를 이용해 문제를 해결하자.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;

int N;
vector<pair<ll, ll>> vec;

vector<ld> dp(1000);
vector<ld> tmp(1000);

ld dist(pair<ll, ll>& p1, pair<ll, ll>& p2) {
	return hypot((ld)(p2.first - p1.first), (ld)(p2.second - p1.second));
}

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

	cout << fixed;
	cout.precision(2);

	cin >> N;
	for (int i = 0; i < N; i++) {
		ll x, y; cin >> x >> y;
		vec.emplace_back(make_pair(x, y));
	}

	sort(vec.begin(), vec.end());

	if (N == 1) cout << 0;
	else {
		dp[0] = dist(vec[0], vec[1]);
		for (int i = 2; i < N; i++) {
			ld dd = dist(vec[i - 1], vec[i]);
			tmp[i - 1] = 1000000000000000007LL;
			for (int j = 0; j < i - 1; j++) {
				tmp[j] = dp[j] + dd;
				tmp[i - 1] = min(tmp[i - 1], dp[j] + dist(vec[j], vec[i]));
			}

			swap(dp, tmp);
		}

		ld ans = 1000000000000000007LL;
		for (int i = 0; i < N - 1; i++) {
			ans = min(ans, dp[i] + dist(vec[i], vec[N - 1]));
		}
		
		cout << ans;
	}
}