취미로 코딩하기

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

이번에 볼 문제는 백준 3088번 문제인 화분 부수기이다.
문제는 아래 링크를 확인하자.

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

뒤의 어떤 화분을 깨더라도 앞의 화분이 깨지지는 않는 다는 점에 착안하면, 무조건 화분을 앞에서부터 깨는 것이 이득임을 알 수 있다.

화분에 써있는 숫자는 100만 이하이므로, 크기 100만의 배열을 만들고 앞서서 해당 숫자가 적힌 화분이 있었는지 확인하는 것으로 문제를 빠르게 해결할 수 있다.

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

#include <iostream>
using namespace std;

bool chk[1000001];

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

	int N; cin >> N;
	int cnt = 0;
	while (N--) {
		int x, y, z; cin >> x >> y >> z;
		if (!(chk[x] || chk[y] || chk[z])) cnt++;
		chk[x] = chk[y] = chk[z] = 1;
	}
	cout << cnt;
}

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

이번에 볼 문제는 백준 13976번 문제인 타일 채우기 2이다.
문제는 아래 링크를 확인하자.

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

N이 적당히 작다면 적당한 DP문제였겠지만, N이 1,000,000,000,000,000,000까지 입력이 들어오므로 일반적인 DP는 사용할 수 없을 것이다. 대신 이 문제는 점화식을 구해, 해당 점화관계를 행렬의 거듭제곱을 통해 O(lgN)의 속도로 계산하는 것으로 해결할 수 있다.

An을 N의 값이 n일 때의 답이라고 하자.

우선, N이 홀수라면 타일을 배치할 수 없으므로 0을 출력한다.

N이 0이라면 아무 타일도 배치하지 않는 하나의 경우의 수가 존재하므로 A0 = 1이다.

N이 2라면 (문제 예제에도 나와있듯이) A2 = 3이다.

N이 4 이상의 짝수라면, 두 경우를 제외하면 "전체 타일이 완전히 세로선으로 두 부분 타일링으로 나뉠 수 있는 곳" 중 가장 오른쪽 선이 존재할 것이고, 이를 바탕으로 식을 세우면 다음과 같은 식을 얻는다.

A_2k = 3 * A_2k-2 + 2 * A_2k-4 + 2 * A_2k-6 + ... + 2 * A0

여기서, A_2k와 A_2k-2를 나타내는 점화식의 차를 구하면 더 간단해진 형태의 점화식을 얻을 수 있다. 이는 직접 해보자.

위에서 얻은 점화식을 이용하여 행렬의 거듭제곱을 통한 빠른 계산을 해주자.

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

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

ll mat[2][2] = { {4,-1},{1,0} };
ll vec[2] = { 3,1 };

ll tmat[3][3];
ll tvec[3];

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

	ll N; cin >> N;
	if (N & 1) cout << 0;
	else {
		N >>= 1;
		N--;
		while (N > 0) {
			if (N & 1) {
				for (int i = 0; i < 2; i++) {
					tvec[i] = 0;
					for (int k = 0; k < 2; k++) {
						tvec[i] += mat[i][k] * vec[k];
					}
				}
				for (int i = 0; i < 2; i++) {
					vec[i] = tvec[i] % 1000000007;
				}
			}

			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					tmat[i][j] = 0;
					for (int k = 0; k < 2; k++) {
						tmat[i][j] += mat[i][k] * mat[k][j];
					}
				}
			}
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					mat[i][j] = tmat[i][j] % 1000000007;
				}
			}
			N >>= 1;
		}

		if (vec[0] < 0) vec[0] += 1000000007;
		cout << vec[0];
	}
}

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

이번에 볼 문제는 백준 5032번 문제인 탄산 음료이다.
문제는 아래 링크를 확인하자.

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

현재 가지고 있는 병의 수가 c보다 큰 동안 while문 등을 통해 계속 탄산 음료를 바꿔 먹는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

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

	int e, f, c; cin >> e >> f >> c;
	int N = e + f;
	int ans = 0;
	while (N >= c) {
		int temp = N / c;
		ans += temp;
		N = N % c + temp;
	}

	cout << ans;
}

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

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

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

주어지는 짝수길이의, 각 자릿수가 0이 아닌 정수를 같은 길이로 앞뒤로 쪼개는 문제이다.

글쓴이는 주어지는 수를 정수로 입력받은 후 substr을 이용하여 문제를 해결하였다.

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

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

int main() {
	string s; cin >> s;
	int slen = s.length() / 2;
	cout << s.substr(0, slen) << ' ' << s.substr(slen, slen);
}

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

이번에 볼 문제는 백준 3745번 문제인 오름세이다.
문제는 아래 링크를 확인하자.

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

매 테스트케이스마다 LIS를 구할 수열이 주어진다.

LIS의 크기를 구하여 매번 출력해주자.

while (cin>>N)과 같은 형식으로 입력을 받으면 EOF가 나오기 전에는 입력을 계속 받고 EOF가 나온 이후에는 반복을 종료할 수 있다.

(세그먼트트리로 LIS 구하기 연습3)

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

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

int seg[262165];

int update(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = qVal;
	return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int rangemax(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

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

	int N;
	while (cin >> N) {
		memset(seg, 0, sizeof(seg));
		int cnt = 0;
		while (N--) {
			int x; cin >> x;
			int temp = rangemax(1, 100000, 1, x - 1, 1) + 1;
			if (temp > cnt) cnt = temp;
			update(1, 100000, x, temp, 1);
		}
		cout << cnt << '\n';
	}
}

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

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

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

다음으로 날아가야하는 새의 마릿수가 남은 새보다 많다면, 1로 초기화하는 조건을 넣어 while문을 이용하자.

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

#include <iostream>
using namespace std;

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

	int N; cin >> N;
	int i = 1;
	int cnt = 0;
	while (N > 0) {
		if (i <= N) {
			N -= i++;
			cnt++;
		}
		else i = 1;
	}

	cout << cnt;
}