취미로 코딩하기

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

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

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

주어진 문제의 상황은 각 체스판의 칸을 노드로 생각하고, 나이트의 움직임으로 이동할 수 있는 칸의 쌍을 에지로 하는 그래프로 모델링할 수 있다.

위와 같은 모델링에서, 주어진 문제는 한 노드에서 다른 노드까지의 최단거리를 구하는 문제와 같게 된다. 이는 BFS를 통해 간단히 알아낼 수 있다.

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

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

int sR, sC, eR, eC;
int dist[8][8];

int dr[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dc[8] = { 2,1,-1,-2,-2,-1,1,2 };

void bfs() {
	queue<pair<int, int>> que;
	que.push(make_pair(sR, sC));
	dist[sR][sC] = 1;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr > 7 || cc < 0 || cc > 7 || dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	string s1, s2; cin >> s1 >> s2;
	sR = s1[0] - 'a', sC = s1[1] - '1', eR = s2[0] - 'a', eC = s2[1] - '1';
	
	bfs();

	cout << dist[eR][eC] - 1;
}

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

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

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

왼쪽부터 접어 폭발물이 왼쪽으로부터 l번째 칸까지 오게(그리고 l번째 칸을 넘기지는 않게) 접는 경우의 수와 오른쪽부터 접어 폭발물이 오른쪽으로부터 r번째 칸까지 오게(그리고 r번째 칸을 넘기지는 않게) 접는 경우의 수를 각각 구할 수 있다면 가능한 모든 l과 r의 쌍들의 경우를 살펴 문제를 해결할 수 있을 것이다. 이와 같은 경우의 수를 DP를 이용해 구해보자. 아래의 서술은 왼쪽에서부터 접는 경우를 기준으로 살펴본다.

dp[C][L]을 "연속해서 C개의 칸에 폭발물이 붙어있는 것이 보이는, 왼쪽으로부터 L번째 칸까지 폭발물이 붙어있는 경우의 수"라 하자. 이 상태로 접기 이전 상태들을 생각해보면, dp[C][L] = dp[C-L][L] + dp[C-L-1][L-1] + ... + dp[C-L-2][L-1] + ... 과 같은 형태의 점화식을 쉽게 떠올릴 수 있다.

이 점화식을 이용해 각 dp[C][L]의 값을 계산해낼 수 있고, 이를 이용하면 폭발물이 왼쪽으로부터 L번째 칸까지 오게(그리고 L번째 칸을 넘기지는 않게) 접는 경우의 수를 각 C별 값을 합하여 계산해낼 수 있다. 이를 이용해 문제를 해결하자.

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

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

int N, A, B;
ll dp1[1001][1001];
bool visited1[1001][1001];
ll total1[1001];

ll dp2[1001][1001];
bool visited2[1001][1001];
ll total2[1001];

ll func1(int i, int j) {
	ll& ret = dp1[i][j];
	if (visited1[i][j]) return ret;
	visited1[i][j] = 1;

	for (int k = 0; k <= i && i - k > 0 && j - i - k > 0; k++) {
		ret += func1(i - k, j - i -  k);
	}

	ret %= MOD;

	return ret;
}

ll func2(int i, int j) {
	ll& ret = dp2[i][j];
	if (visited2[i][j]) return ret;
	visited2[i][j] = 1;

	if (2 * i > j) return ret;

	for (int k = 0; k <= i && i - k > 0 && j - i - k > 0; k++) {
		ret += func2(i - k, j - i - k);
	}

	return ret %= MOD;
}

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

	cin >> N >> A >> B;
	dp1[A][A] = dp2[B][B] = 1;
	visited1[A][A] = visited2[B][B] = 1;
	for (int i = 1; i < 1001; i++) {
		for (int j = i; j < 1001; j++) func1(i, j);
	}
	for (int i = 1; i < 1001; i++) {
		for (int j = i; j < 1001; j++) func2(i, j);
	}

	for (int j = 1; j < 1001; j++) {
		for (int i = 1; i <= j; i++) {
			total1[j] += dp1[i][j], total2[j] += dp2[i][j];
		}
		total1[j] %= MOD, total2[j] %= MOD;
	}

	ll ans = 0;
	for (int L = 1; L < N; L++) {
		for (int R = 1; L + R <= N; R++) {
			ans += total1[L] * total2[R];
		}
		ans %= MOD;
	}

	cout << ans;
}

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

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

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

각 procedure을 같은 X값끼리 묶어 값별로 한 번씩 시뮬레이션한 뒤(\(O(NlgN)\)), 누적합 배열을 만들어(\(O(N)\)) 각 쿼리를 처리해(쿼리당 \(O(1)\)) 문제를 해결하자.

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

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

int N, K, Q;
ll cnt[1000001];
ll psum[1000000];

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

	cin >> N >> K;
	while (K--) {
		int x; cin >> x;
		cnt[x]++;
	}

	for (int i = 1; i <= N; i++) {
		ll& curcnt = cnt[i];
		if (curcnt) {
			for (int k = 0; k < N; k += i) psum[k] += curcnt;
		}
	}

	for (int i = 1; i < N; i++) psum[i] += psum[i - 1];

	cin >> Q;
	while (Q--) {
		int L, R; cin >> L >> R;
		ll ans;
		if (L) cout << psum[R] - psum[L - 1] << '\n';
		else cout << psum[R] << '\n';
	}
}

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

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

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

3xn 직사각형을 1x2 타일을 이용해 채우는 경우의 수를 묻는 문제이다.

n이 홀수이면 채워야하는 전체 칸이 총 홀수개가 되므로 어떻게 해도 직사각형을 타일을 이용해 채울 수 없다.

그렇지 않은 경우, "맨 왼쪽부터 시작해 처음으로 부분직사각형으로 끊을 수 있는 위치"가 모든 타일링에 존재한다는 점을 이용해 dp식을 세워 문제를 해결할 수 있다. 구체적인 식은 아래의 코드를 참고하자.

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

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

ll dp[501];

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

	dp[1] = 3, dp[2] = 11;
	for (int i = 3; i < 501; i++) {
		dp[i] = 2 + 3 * dp[i - 1] + 6;
		for (int k = 2; k < i - 1; k++) {
			dp[i] += 2 * dp[i - k];
		}

		dp[i] %= MOD;
	}

	int N; cin >> N;
	if (N & 1) cout << 0;
	else cout << dp[N/2];
}

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

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

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

각 문자열이 문제에서 요구하는 다섯가지 조건을 만족하는지를 판단하는 문제이다.

테스트케이스의 수가 충분히 적고 문자열의 길이가 충분히 짧으므로 각 문자가 각 조건을 만족하는 문자인지를 일일 확인하는 것으로 문제를 해결할 수 있다.

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

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

int cnt[128];
string symbols = "+_)(*&^%$#@!./,;{}";

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

	int T; cin >> T;
	while (T--) {
		bool chk1 = 0, chk2 = 0, chk3 = 0, chk4 = 0, chk5 = 0;
		int slen; string s; cin >> slen >> s;
		for (auto l : s) {
			if ('a' <= l && l <= 'z') chk1 = 1;
			if ('A' <= l && l <= 'Z') chk2 = 1;
			if ('0' <= l && l <= '9') chk3 = 1;
			for (auto sym : symbols) {
				if (sym == l) chk4 = 1;
			}
		}
		if (slen >= 12) chk5 = 1;

		if (chk1 && chk2 && chk3 && chk4 && chk5) cout << "valid\n";
		else cout << "invalid\n";
	}
}

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

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

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

주어지는 문자열의 각 문자의 개수를 세는 배열을 만들어 문제를 해결하자.

문제 조건에 따라 가장 많은 개수가 있는 문자는 유일하게 주어지므로 안심하고 구현하자.

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

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

int cnt[128];

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

	int slen; string s; cin >> slen >> s;
	for (auto l : s) cnt[l]++;
	int mx = 0; char ans;
	for (char i = 'a'; i <= 'z'; i++) {
		if (cnt[i] > mx) {
			mx = cnt[i];
			ans = i;
		}
	}

	cout << ans << ' ' << mx;
}