취미로 코딩하기

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

이번에 볼 문제는 백준 28294번 문제인 프랙탈이다.
문제는 아래 링크를 확인하자.

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

한 변의 길이가 $N^a$인 정$N$각형에 문제에서 주어진 작업을 $k$번 반복한 도형의, 다음 작업때 변형되는 에지의 개수를 $e_{N,a}$, 둘레의 길이를 $l_{N,a}$라 하자.

이 때 다음 두 식이 성립함을 관찰하자.

$e_{N,a+1}=(N-1)e_{N,a}$

$l_{N,a+1}=(N-2)e_{N,a}+(N-1)l_{N,a}$

첫 식은 변형되는 에지마다 $N$각형 모양이 하나씩 생기는 것을 관찰하는 것으로, 두 번째 식은 먼저 기존 도형을 $N$배 확대한 다음 추가되는 길이 $(N-1)e_{N,a}$ 및 지워지는 길이 $e_{N,a}$를 관찰하는 것으로 간단히 세울 수 있다.

위 점화관계를 행렬로 표현한 뒤, binary exponentiaion을 이용해 문제의 답 $l_{N,a}$을 계산하는 것으로 문제를 해결하자.

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

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

ll N, a;
ll mat[2][2], vec[2];
ll tmp[2][2], vtmp[2];

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

	cin >> N >> a;
	mat[0][0] = N - 1, mat[1][0] = N - 2, mat[1][1] = N, vec[0] = N, vec[1] = N;

	while (a) {
		if (a & 1) {
			vtmp[0] = mat[0][0] * vec[0] + mat[0][1] * vec[1];
			vtmp[1] = mat[1][0] * vec[0] + mat[1][1] * vec[1];
			vec[0] = vtmp[0] % MOD, vec[1] = vtmp[1] % MOD;
		}
		tmp[0][0] = mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0];
		tmp[0][1] = mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1];
		tmp[1][0] = mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0];
		tmp[1][1] = mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1];

		mat[0][0] = tmp[0][0] % MOD;
		mat[0][1] = tmp[0][1] % MOD;
		mat[1][0] = tmp[1][0] % MOD;
		mat[1][1] = tmp[1][1] % MOD;

		a >>= 1;
	}

	cout << vec[1];
}

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

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

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

어떤 양의 정수 $N$의 자릿수는 상용로그 $lo{g}_{10}N$의 지표 + 1과 같이 계산할 수 있음을 상기하자. 이 식을 이용해 문제를 해결할 수 있다.

C++에서 상용로그는 cmath 헤더의 log10 함수를 이용해 간단히 계산할 수 있다. 이 때, 실수 연산의 정밀도를 위해 gcc에서 128비트로 구현된 long double을 이용해주자.

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

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

int A, B;

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

	cin >> A >> B;
	cout << (int)(log10((ld)A) * B) + 1;
}

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

이번에 볼 문제는 백준 28291번 문제인 레드스톤이다.
문제는 아래 링크를 확인하자.

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

50x50 배열을 이용해 주어진 레드스톤 회로 블록 배치들을 표현한 뒤, 해당 배열 위에서 회로를 따라 모든 레드스톤 블록으로부터 레드스톤 램프까지 거리 15 이내로 도달할 수 있는지를 판단해 문제를 해결하자. 이는 BFS 등을 이용해 구현할 수 있다.

각 레드스톤 램프는 전기신호를 다시 전달하지 않음에 유의하자.

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

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

int R, C, N;
int board[52][52];
int dist[52][52];
queue<pair<int, int>> que;
int cnt;

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

void bfs() {
	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 (dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] - 1;
			if (!dist[rr][cc]) continue;
			if (board[rr][cc] == 1) que.push(make_pair(rr, cc));
			else if (board[rr][cc] == 2) board[rr][cc] = 0, cnt--;
		}
	}
}

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

	cin >> C >> R >> N;
	while (N--) {
		string s; int r, c;
		cin >> s >> c >> r;
		r++, c++;

		if (s[9] == 'b') dist[r][c] = 16, que.push(make_pair(r, c));
		else if (s[9] == 'd') board[r][c] = 1;
		else board[r][c] = 2, cnt++;
	}

	bfs();

	if (cnt) cout << "failed";
	else cout << "success";
}

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

이번에 볼 문제는 백준 28292번 문제인 개미 수열이다.
문제는 아래 링크를 확인하자.

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

개미 수열을 이루는 n(>2)번째 문자열을 이용해 n+1번째 문자열을 만드는 과정을 생각해보자. 숫자 a가 n개 연속으로 등장하고 b가 m개 연속으로 등장한다는 의미로 anbm과 같이 문자열을 작성할 때, a와 b는 항상 다르다는 점을 관찰하자. 이 관찰을 이용하면 문제의 답은 3을 넘을 수 없음을 알 수 있다.

또한 이전 문자열에 등장한 숫자 k는 다음 문자열에도 "k가 (k의 개수)개"와 같은 형태로 항상 재등장한다는 점을 관찰하자.

위의 두 관찰과 개미 수열의 앞 몇 항을 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	if (N < 3) cout << 1;
	else if (N < 6) cout << 2;
	else cout << 3;
}

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

이번에 볼 문제는 백준 28290번 문제인 안밖? 밖안? 계단? 역계단?이다.
문제는 아래 링크를 확인하자.

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

지문에 주어진 6가지 문자열 입력에 대해 각 문자열에 대응되는 문제의 답을, 나머지 문자열 입력에 대해 "molu"를 출력하는 문제이다.

이는 문제의 답을 기준으로 조건문을 이용하는 것으로 간단히 구현할 수 있다.

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

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

string s;

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

	cin >> s;
	if (s == "fdsajkl;" || s == "jkl;fdsa") cout << "in-out";
	else if (s == "asdf;lkj" || s == ";lkjasdf") cout << "out-in";
	else if (s == "asdfjkl;") cout << "stairs";
	else if (s == ";lkjfdsa") cout << "reverse";
	else cout << "molu";
}

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

이번에 볼 문제는 백준 28289번 문제인 과 조사하기이다.
문제는 아래 링크를 확인하자.

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

1학년 학생 수를 저장하는 변수, 그렇지 않은 학생 중 반이 1반 또는 2반인 학생 수를 저장하는 변수, 3반인 학생 수를 저장하는 변수, 4반인 학생 수를 저장하는 변수를 선언하자. 그리고 적절한 조건문을 통해 각 주어지는 학생 정보 입력을 처리하고 문제를 해결하자.

학생의 정보 $N_p$는 문제 풀이에 사용하지 않지만 입력을 받기는 해야 함에 유의해 구현하자.

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

#include <iostream>
using namespace std;

int P;
int x12, x3, x4, x0;

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

	cin >> P;
	while (P--) {
		int g, c, n; cin >> g >> c >> n;
		if (g < 2) x0++;
		else if (c < 3) x12++;
		else if (c < 4) x3++;
		else x4++;
	}

	cout << x12 << '\n' << x3 << '\n' << x4 << '\n' << x0;
}