취미로 코딩하기

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

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

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

좌상단의 칸에서 우하단의 칸으로 우측 방향과 아래 방향으로의 인접한, 0이 아닌 칸으로의 이동만을 이용한 경로 중 그 경로상의 칸에 적힌 모든 정수의 곱을 10진수로 나타냈을 때의 trailing zero의 최소 개수를 묻는 문제이다. (좌상단에서 우하단으로 이동이 가능한 입력만 주어짐을 문제가 보장한다.)

어떤 경로 T가 trailing zero가 최소가 되게 하는 경로 중 하나라고 해보자. 그리고 이 때 T 위의 모든 칸의 정수를 곱한 수가 소인수로 2를 p개, 5를 q개 가지고 있다고 해보자. 여기서 p<=q라면 모든 경로에 대하여 모든 칸의 정수를 곱한 수가 가지는 소인수 2의 개수가 p 이하여야 하고 마찬가지로 p>=q라면 모든 경로에 대하여 모든 칸의 정수를 곱한 수가 가지는 소인수 5의 개수가 q 이하여야 함을 관찰하자.

위의 관찰에 따라, 문제의 답은 좌상단 칸에서 우하단 칸으로 이동하는 경로 중 모든 칸의 정수를 곱한 수가 가지는 (소인수 2의 개수가 최소인 경로의 2의 개수)와 (소인수 5의 개수가 최소인 경로의 5의 개수) 두 값중 더 작은 값임을 알 수 있다.

이는 dp를 이용해 $O(N^2)$에 계산할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int arr[1000][1000];
int dp[1000][1000][2];
int cnt2, cnt5;

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

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

	while (arr[0][0] % 2 == 0) arr[0][0] /= 2, cnt2++;
	while (arr[0][0] % 5 == 0) arr[0][0] /= 5, cnt5++;
	dp[0][0][0] = cnt2, dp[0][0][1] = cnt5;

	for (int c = 1; c < N; c++) {
		int& arr0c = arr[0][c];
		if (arr0c == 0) dp[0][c][0] = dp[0][c][1] = 1000000007;
		else {
			cnt2 = cnt5 = 0;
			while (arr0c % 2 == 0) arr0c /= 2, cnt2++;
			while (arr0c % 5 == 0) arr0c /= 5, cnt5++;
			dp[0][c][0] = min(dp[0][c - 1][0] + cnt2, 1000000007), dp[0][c][1] = min(dp[0][c - 1][1] + cnt5, 1000000007);
		}
	}

	for (int r = 1; r < N; r++) {
		int& arrr0 = arr[r][0];
		if (arrr0 == 0) dp[r][0][0] = dp[r][0][1] = 1000000007;
		else {
			cnt2 = cnt5 = 0;
			while (arrr0 % 2 == 0) arrr0 /= 2, cnt2++;
			while (arrr0 % 5 == 0) arrr0 /= 5, cnt5++;
			dp[r][0][0] = min(dp[r - 1][0][0] + cnt2, 1000000007), dp[r][0][1] = min(dp[r - 1][0][1] + cnt5, 1000000007);
		}
	}

	for (int r = 1; r < N; r++) {
		for (int c = 1; c < N; c++) {
			int& arrrc = arr[r][c];
			if (arrrc == 0) dp[r][c][0] = dp[r][c][1] = 1000000007;
			else {
				cnt2 = cnt5 = 0;
				while (arrrc % 2 == 0) arrrc /= 2, cnt2++;
				while (arrrc % 5 == 0) arrrc /= 5, cnt5++;
				dp[r][c][0] = min(dp[r - 1][c][0], dp[r][c - 1][0]) + cnt2, dp[r][c][1] = min(dp[r - 1][c][1], dp[r][c - 1][1]) + cnt5;
			}
		}
	}

	cout << min(dp[N - 1][N - 1][0], dp[N - 1][N - 1][1]);
}

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

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

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

문제에서 주어진 대로 문자열을 처리해 출력하는 문제이다.

이 문제에서 letters란 'A'-'Z', 'a'-'z'를 의미하는 것임에 유의하자. 즉, 먼저 나오는 1/3개의 letters는 알파벳 대소문자 중 먼저 나오는 1/3개의 문자를 의미함에 유의하자.

letters가 K개일 때, 앞선 1/3개의 letters는 (K+1)/3, 2/3개의 letters는 (K*2+1)/3으로 계산할 수 있다는 점을 이용하면 반올림 구현을 간단하게 해낼 수 있다. (단, 여기서 '/'는 몫연산이다.)

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

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

int slen;
string s;
int lcnt;
bool isvowel[128];
bool vowelleft;

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

	isvowel['a'] = isvowel['e'] = isvowel['i'] = isvowel['o'] = isvowel['u'] = isvowel['A'] = isvowel['E'] = isvowel['I'] = isvowel['O'] = isvowel['U'] = 1;

	getline(cin, s);
	slen = s.length();

	for (auto& l : s) {
		if (('A' <= l && l <= 'Z') || ('a' <= l && l <= 'z')) cout << '.', lcnt++;
		else cout << l;
	}
	cout << '\n';

	for (int i = 0, cnt = 0; i < slen; i++) {
		auto& l = s[i];
		if (('A' <= l && l <= 'Z') || ('a' <= l && l <= 'z')) {
			if (cnt < (lcnt + 1) / 3) cnt++, cout << l;
			else cout << '.';
		}
		else cout << l;
	}
	cout << '\n';

	for (int i = 0, cnt = 0; i < slen; i++) {
		auto& l = s[i];
		if (('A' <= l && l <= 'Z') || ('a' <= l && l <= 'z')) {
			if (cnt < (lcnt + 1) / 3) cnt++;
			else {
				if (isvowel[l]) vowelleft = 1;
			}
		}
	}

	if (vowelleft) {
		for (int i = 0, cnt = 0; i < slen; i++) {
			auto& l = s[i];
			if (('A' <= l && l <= 'Z') || ('a' <= l && l <= 'z')) {
				if (cnt < (lcnt + 1) / 3) cnt++, cout << l;
				else if (isvowel[l]) cout << l;
				else cout << '.';
			}
			else cout << l;
		}
	}
	else {
		for (int i = 0, cnt = 0; i < slen; i++) {
			auto& l = s[i];
			if (('A' <= l && l <= 'Z') || ('a' <= l && l <= 'z')) {
				if (cnt < (lcnt * 2 + 1) / 3) cnt++, cout << l;
				else cout << '.';
			}
			else cout << l;
		}
	}
}

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

이번에 볼 문제는 백준 2079번 문제인 팰린드롬이다.
문제는 아래 링크를 확인하자.

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

모든 팰린드롬 문자열은 그 길이가 3 이상이라면 양 끝의 두 문자를 지워도 다시 팰린드롬 문자열이 됨을 상기하자.

따라서, 가운데를 담당할 문자 하나 또는 둘을 먼저 고르고 양 옆에 문자를 하나씩 이어나가 팰린드롬 성질이 깨질 때까지 살피는 것으로 주어진 문자열에 존재하는 모든 팰린드롬 문자열에 한번씩 접근할 수 있게 된다.

dp[j]를 주어진 문자열의 [0,j] 구간에 해당하는 부분문자열에 대하여 이를 최소 개수의 팰린드롬으로 분할할 때의 개수라 하면 이는 [i,j] 구간에 해당하는 부분무자열이 팰린드롬인 모든 i에 대하여 dp[i - 1] + 1의 최솟값으로 계산할 수 있음을 관찰하자.

위의 관계를 인덱스를 노드, [i,j] 구간을 i에서 j+1로 향하는 에지로 하는 그래프로 모델링하자. 이 때 주어진 문제는 0번 인덱스에서 (문자열의 길이)번 인덱스까지 향하는 최단거리 문제로 바꾸어 생각할 수 있게 된다. BFS 등을 이용해 해당하는 최단거리를 구하고 문제를 해결하자.

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

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

string s; int slen;
vector<int> G[2001];
int dist[2001];

void bfs() {
	queue<int> que;
	que.push(0);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

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

	cin >> s; slen = s.length();
	for (int mid = 0; mid < slen; mid++) { // 홀수길이 팰린드롬
		int L = mid, R = mid;
		while (-1 < L && R < slen && s[L] == s[R]) {
			G[L].emplace_back(R + 1);
			L--, R++;
		}
	}
	for (int midL = 0, midR = 1; midR < slen; midL++, midR++) { // 짝수길이 팰린드롬
		int L = midL, R = midR;
		while (-1 < L && R < slen && s[L] == s[R]) {
			G[L].emplace_back(R + 1);
			L--, R++;
		}
	}

	bfs();

	cout << dist[slen];
}

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

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

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

소지한 달러를 A환율로 마르크로 바꾼 뒤 B환율로 다시 달러로 바꾸면 소지한 달러는 A/B배로 증가한다.

매 연속한 두 날 사이의 환율을 보며 위와 같은 환전으로 이득을 볼 수 있을 때마다(즉 A/B>1일 때마다) 환전을 반복하는 것으로 문제를 해결하자.

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

#include <iostream>
using namespace std;
typedef long double ld;

ld ans = 100;
ld prv = 0;

int N;

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

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

	cin >> N;
	while (N--) {
		ld cur; cin >> cur;
		if (prv > cur) ans *= (prv / cur);
		prv = cur;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 3186번 문제인 소변기이다.
문제는 아래 링크를 확인하자.

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

주어지는 시각별 센서의 인식을 읽으면서, 1) "사용중"이 아닌 상태일 경우 지금까지의 연속한 '1'의 개수를 세어 그 개수가 K 이상이면 "사용중" 상태로 바꾸고 2) "사용중" 상태일 경우 지금까지의 연속한 '0'의 개수를 세어 그 개수가 L 이상이면 "완료" 수행을 한 뒤 "사용중"이 아닌 상태로 돌아가는 시뮬레이션 코드를 작성해 문제를 해결하자.

문자열로 주어진 시간을 모두 처리한 뒤에도 센서가 "사용중" 상태일 경우 적절한 시각 뒤에 "완료" 수행을 하게 됨을 놓치지 말자.

"완료" 수행을 했는지 여부를 확인하는 변수를 만들면 모든 수행을 마친 뒤 "NIKAD"를 출력할 지 여부를 결정할 수 있다.

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

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

int K, L, N;
string s;
int combo, sgn;
bool flushed;

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

	cin >> K >> L >> N >> s;

	for (int i = 0; i < N; i++) {
		if (sgn) {
			if (s[i] == '0') {
				combo++;
				if (combo == L) flushed = 1, cout << i + 1 << '\n', combo = 0, sgn = 0;
			}
			else combo = 0;
		}
		else {
			if (s[i] == '1') {
				combo++;
				if (combo == K) combo = 0, sgn = 1;
			}
			else combo = 0;
		}
	}

	if (sgn) flushed = 1, cout << N + (L - combo);

	if (!flushed) cout << "NIKAD";
}

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

이번에 볼 문제는 백준 3187번 문제인 양치기 꿍이다.
문제는 아래 링크를 확인하자.

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

3184번 문제(링크)와 양을 나타내는 문자('k'와 'o')만이 다른, 사실상 같은 문제이다. 해당 문제의 풀이글을 참고해 문제를 해결하자.

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

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

int R, C;
string board[250];
int kcnt, vcnt;

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

void bfs(int qr, int qc) {
int K = 0, V = 0;
if (board[qr][qc] == 'k') K++;
else if (board[qr][qc] == 'v') V++;
board[qr][qc] = '#';

queue<pair<int, int>> que;
que.push(make_pair(qr, qc));

while (!que.empty()) {
int r = que.front().first, c = que.front().second; que.pop();
for (int i = 0; i < 4; i++) {
int rr = r + dr[i], cc = c + dc[i];
if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == '#') continue;
if (board[rr][cc] == 'k') K++;
else if (board[rr][cc] == 'v') V++;
board[rr][cc] = '#';
que.push(make_pair(rr, cc));
}
}

if (K > V) kcnt += K;
else vcnt += V;
}

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

cin >> R >> C;
for (int r = 0; r < R; r++) cin >> board[r];

for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (board[r][c] != '#') {
bfs(r, c);
}
}
}

cout << kcnt << ' ' << vcnt;
}