취미로 코딩하기

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

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

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

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

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

이번에 볼 문제는 백준 3182번 문제인 한동이는 공부가 하기 싫어!이다.
문제는 아래 링크를 확인하자.

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

각 선배에 대하여 해당 선배부터 질문을 시작할 때 만나게 되는 선배의 수는 \(N\) 이하임을 알 수 있다. 전체 선배의 수가 1000명이므로, 모든 각 선배에 대하여 질문을 시작해보더라도 선배에게 질문을 하는 횟수는 \(N^2\) 이하임을 알 수 있다.

따라서 모든 선배에 대하여 그 선배부터 질문을 시작할 때 총 몇 명의 선배를 만나게 되는지를 구하는 시뮬레이션을 각각 돌려 문제를 해결하는 방법은 문제를 해결하기에 충분한 시간복잡도를 가진다. 이와 같은 방법으로 문제를 해결하자.

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

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

int N;
int arr[1001];
int visited[1001];

int ans, mx;

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		int cnt = 0, idx = i;
		while (!visited[idx]) {
			visited[idx] = 1;
			idx = arr[idx];
			cnt++;
		}
		if (mx < cnt) mx = cnt, ans = i;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 3181번 문제인 줄임말 만들기이다.
문제는 아래 링크를 확인하자.

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

주어져있는 "쓸모없는 단어"를 제외한 단어들의 첫 문자들을 대문자로 이어 출력하는 문제이다. 단, 첫 단어의 첫 문자는 항상 (대문자로) 출력해주어야 한다.

각 단어가 "쓸모없는 단어"인지를 판단하는 것은 set 자료구조를 이용해 아래와 같이 간단히 구현할 수 있다.

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

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

string s;
set<string> st = { "a", "ali", "i" , "ili", "nego", "ni", "niti", "no", "pa", "te" };

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

	cin >> s; cout << (char)toupper(s[0]);
	while (cin >> s) {
		if (st.find(s) == st.end()) cout << (char)toupper(s[0]);
	}
}