취미로 코딩하기

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

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

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

초항과 두번째 항이 각각 1인 피보나치수열에 대하여 피보나치수열의 x번째 항과 y번째 항의 gcd는 피보나치수열의 gcd(x,y)번째 항과 같다는 성질을 이용하여 문제를 해결하자.

또한, 점화식을 빠르게 계산하기 위해 binary exponentiation을 이용하면 문제를 해결할 수 있다.

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

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

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

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

	int T; cin >> T;
	while (T--) {
		int x, y; cin >> x >> y;
		int gcdxy = gcd(x, y);
		ll mat[2][2] = {{1,1},{1,0}};
		ll vec[2] = { 1,0 };
		
		while (gcdxy > 0) {
			if (gcdxy & 1) {
				ll temp = (mat[0][0] * vec[0] + mat[0][1] * vec[1])%1000000007;
				vec[1] = (mat[1][0] * vec[0] + mat[1][1] * vec[1])%1000000007;
				vec[0] = temp;
			}
			ll mat00 = (mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0]) % 1000000007;
			ll mat01 = (mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]) % 1000000007;
			ll mat10 = (mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0]) % 1000000007;
			ll mat11 = (mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]) % 1000000007;
			mat[0][0] = mat00, mat[0][1] = mat01, mat[1][0] = mat10, mat[1][1] = mat11;
			
			gcdxy >>= 1;
		}

		cout << vec[1] << '\n';
	}
}

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

이번에 볼 문제는 백준 17080번 문제인 결함 게임이다.
문제는 아래 링크를 확인하자.

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

게임이론 문제이다.

적은 개수의 돌의 경우를 먼저 살펴보면 다음과 같다:

돌이 1개 있다면 탑이 하나밖에 만들어질 수 없으므로 선공의 승리이다.

돌이 2개 있다면 선공이 2인 돌을 먼저 골라 탑을 1개로 유도할 수 있으므로 선공의 승리이다.

돌이 3개 있다면 선공이 무엇을 골라도 후공이 탑을 2개로 유도할 수 있다.

(선공이 1을 고른다면 후공이 3을 골라 탑 2개로 유도할 수 있고, 선공이 2 또는 3을 고른다면 후공이 1을 골라 탑 2개로 유도할 수 있다.)

돌이 4개 있다면 선공이 2를 고른 후 후공이 (강제로) 1을 고르면 선공이 3을 고르는 것으로 탑 3개를 만들어 승리할 수 있다.

이를 일반화해보자.

1) 돌이 짝수개이면 선공의 승리이다. 전략은 다음과 같다:

돌이 두개 남기 전까지 선공은 두번째로 작은 돌만을 계속 골라 새로운 돌탑의 바닥으로 한다. 후공은 남은 가장 작은 돌을 그 위에 올리는 행동밖에 할 수 없다.

마지막 남은 돌 2개로 탑 1개 또는 2개를 만드는 것을 강요하여 선공이 승리를 차지한다.

2) 돌이 4n+1개 꼴이면 선공의 승리이다. 전략은 다음과 같다:

돌 1개 남을 때까지 두번째로 작은 돌만을 계속 골라 새로운 바닥의 돌탑으로 하면 짝수개의 돌탑이 만들어진다. 남은 하나의 돌을 새로 배치하여 홀수개의 돌탑을 만든다.

3) 돌이 4n+3개 꼴이면 후공의 승리이다. 전략은 다음과 같다:

Case 1) 선공이 첫 번째 돌을 집어간 경우:

남아있는 돌은 짝수개이다. 돌이 2개 남을 때까지 두번째로 작은 돌만을 계속 골라 새로운 바닥의 돌탑으로 하자. 이 때, 만들어진 돌탑의 개수에 따라 남은 돌중 작은 돌을 선택할지 큰 돌을 선택할지 결정한다.

Case 2) 선공이 첫 번째 돌이 아닌 돌을 집어간 경우:

후공은 첫번째 돌을 가져간다. 다음 선공의 행동을 기다린다.

Case 2-0) 돌이 하나 남은 경우:

선공은 남은 돌을 배치한다. 이것으로 짝수개의 돌탑이 완성되었으므로 후공의 승리이다.

Case 2-1) 선공이 첫 번째 돌을 집어간 경우:

"Case 1"의 과정을 반복한다.

Case 2-2) 선공이 첫 번째 돌이 아닌 돌을 집어간 경우:

후공은 첫번째 돌을 가져간다. 이제, 처음으로 돌아간다.

따라서, 위의 내용을 구현하는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

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

	int N; cin >> N;
	if (N % 4 == 3) cout << 2;
	else cout << 1;
}

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

이번에 볼 문제는 백준 2655번 문제인 가장높은탑쌓기이다.
문제는 아래 링크를 확인하자.

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

이 문제에서는 만들 수 있는 가장 높은 탑을 쌓을 때, 그 탑을 구성하는 벽돌의 개수와 그 순서를 탑의 위에서부터 출력하는 문제이다.

글쓴이는 위상정렬을 이용하여 문제를 해결하였다.

벽돌이 최대 100개이므로, 두개의 벽돌을 고르는 모든 경우에 대하여 한 벽돌이 다른 벽돌 위에 올라갈 수 있는지를 판단해 가능하다면 directed edge를 긋는 방식으로 방향그래프를 만들 수 있다. 이 그래프는 DAG가 될 수밖에 없으며, 이 그래프를 이용하여 위상정렬을 하면 문제를 해결할 수 있다.

이 탑을 구성하는 벽돌은 위상정렬 과정에서 각 노드로 도달한 경로들을 기록한 뒤 역추적하는 것으로 구할 수 있다.

굳이 그래프를 만들어 위상정렬을 하지 않더라도, 한 가지 기준으로 먼저 정렬을 한 뒤 단순히 DP를 하는 방식으로도 문제를 해결할 수 있을 것으로 보인다.

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

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

int arr[101][3]; // 0:넓이, 1:무게, 2:높이
int cnt[101];
vector<int> G[101];
queue<int> que;
int height[101];
int parent[101];

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

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

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			if (arr[i][0] > arr[j][0] && arr[i][1] > arr[j][1]) {
				G[i].push_back(j);
				cnt[j]++;
			}
			else if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
				G[j].push_back(i);
				cnt[i]++;
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		if (!cnt[i]) que.push(i);
	}

	while (!que.empty()) {
		int current = que.front(); que.pop();
		height[current] += arr[current][2];
		for (auto node : G[current]) {
			if (height[node] < height[current]) {
				height[node] = height[current];
				parent[node] = current;
			}
			cnt[node]--;
			if (cnt[node] == 0) que.push(node);
		}
	}

	int mxheight = 0;
	int mxidx;
	for (int i = 1; i <= N; i++) {
		if (mxheight < height[i]) {
			mxheight = height[i];
			mxidx = i;
		}
	}

	que.push(mxidx);
	while (parent[mxidx] > 0) {
		mxidx = parent[mxidx];
		que.push(mxidx);
	}

	cout << que.size() << '\n';
	while (!que.empty()) {
		cout << que.front() << '\n';
		que.pop();
	}
}

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

이번에 볼 문제는 백준 1932번 문제인 정수 삼각형이다.
문제는 아래 링크를 확인하자.

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

대표적인 기본 DP 문제 중 하나이다.

삼각형의 각 숫자까지의 경로 중 수의 합이 가장 큰 경로는 그 수로 올 수 있는 이전 행의 숫자까지의 숫자의 합이 최대인 경로의 끝에 그 숫자를 붙이는 것으로 구할 수 있다. 이는 DP를 이용하여 쉽게 계산할 수 있다.

아래의 구현이 가능한 이유는 모든 숫자가 음이 아닌 정수이기 때문이다.

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

#include <iostream>
using namespace std;

int arr[501][501];

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

    int N; cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            int x; cin >> x;
            arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + x;
        }
    }
    
    int ans = 0;
    for (int j = 1; j <= N; j++) {
        ans = max(ans, arr[N][j]);
    }

    cout << ans;
}

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

이번에 볼 문제는 백준 2631번 문제인 줄세우기이다.
문제는 아래 링크를 확인하자.

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

최소 몇 명을 움직여야 하는가 라는 문제 대신, 최대 몇 명을 움직이지 않아도 되는가 라는 문제를 생각해보자.

움직이지 않아도 되는 사람들 수는 현재 상태 그대로 있어도 줄이 제대로 서져있는, 즉 LIS를 이루고 있는 사람들을 의미한다.

따라서, 전체 인원 수에서 LIS의 길이를 빼주는 것으로 이 문제를 해결할 수 있다.

아래의 LIS 구현은 세그먼트트리를 이용한 구현이지만, DP로 구현하여도 상관없다.

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

#include <iostream>
using namespace std;

int seg[513];

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; cin >> N;
    for (int i = 0; i < N; i++) {
        int x; cin >> x;
        int temp = rangemax(1, N, 1, x, 1);
        update(1, N, x, temp + 1, 1);
    }

    cout << N - seg[1];
}

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

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

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

주어진 수열에서 최대한 긴 팰린드롬 부분수열을 찾고, 그 외의 숫자들을 추가로 써넣는 것으로 문제를 해결할 수 있다.

가장 긴 팰린드롬 부분수열은 주어진 수열과 그 역순인 수열 사이의 LCS로 구할 수 있다. 증명은 그림으로 그려보면 간단하게 보이니 한번 생각해보자.

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

#include <iostream>
using namespace std;

int arr[5001];

int ans = 0;
int dp[5001][5001];

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

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

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i] == arr[N + 1 - j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			ans = max(ans, dp[i][j]);
		}
	}

	cout << N - ans;
}