취미로 코딩하기

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

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

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

어떤 삼각형의 세 높이가 주어질 때, 해당 삼각형의 넓이를 구하는 문제이다.

삼각형의 세 변의 길이를 \(a\), \(b\), \(c\)라 하고 각 변을 밑변으로 할 때의 삼각형의 높이를 \(h_a\), \(h_b\), \(h_c\)라 하자. 그리고 구하고자 하는 값인 삼각형의 넓이를 \(S\)라 하자. 이때, 삼각형의 넓이공식에 따라 \(a=2S/h_a\), \(b=2S/h_b\), \(c=2S/h_c\)이 성립한다.

한편, 삼각형의 세 변의 길이를 알면 헤론의 공식(Heron's Formula)를 이용해 삼각형의 넓이를 계산할 수 있음(고등학교 과정)을 기억하자. 해당 공식은 다음과 같다:
\(S=\sqrt{s(s-a)(s-b)(s-c)}\) (단, \(s=\frac{a+b+c}{2}\))

헤론의 공식에 위에서 구한 \(a\), \(b\), \(c\)의 \(h\)들로 나타난 표현을 집어넣어 식을 정리하면 \(S\)를 \(h_a\), \(h_b\), \(h_c\)로 나타낸 식을 얻을 수 있다. 이를 이용해 문제를 해결하자.

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

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

ld A, B, C, s;

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

	cin >> A >> B >> C;
	A = (ld)1 / A, B = (ld)1 / B, C = (ld)1 / C;
	s = A + B + C;

	cout << fixed;
	cout.precision(10);
	cout << (ld)1 / sqrt(s * (s - A * 2) * (s - B * 2) * (s - C * 2));
}

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

이번에 볼 문제는 백준 10330번 문제인 과일 서리이다.
문제는 아래 링크를 확인하자.

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

지문에 서술되어 있듯이, 연속 코드의 형태로 주어진 문자열은 '0'으로 시작하는 것과 '1'로 시작하는 것 두 종류가 있다. 각 문자열에 대하여 (1) 비트의 순열로 주어진 문자열로부터 해당 문자열을 만들 수 있는지, 그리고 (2) 그 때 필요한 연산의 수는 얼마인지를 계산해 문제를 해결하자.

어떤 문자열이 다른 문자열로 바뀔 수 있을 필요충분조건은 각 문자열을 구성하는 문자가 같은 것과 같다. (증명은 어렵지 않으므로 생략한다.)

한편, 원래의 문자열에서 같은 비트를 가진 두 인덱스 \(i<j\)에 대응되는 문자가 변환된 문자열에서 위치하는 인덱스를 각각 \(f_i\), \(f_j\)라 할 때 최종 문자열에서 \(f_i>f_j\)와 같이 변환된 경우 항상 \(f_i<f_j\)가 되게끔 변환 과정을 수정할 수 있음을 관찰하자. \(f_i>f_j\)가 되려면 두 인덱스가 가리키던 두 문자가 인접해 있던 순간이 존재해 그 둘을 직접 바꾸는 순간이 있어야하는데, 이 둘을 바꾸는 과정을 지워도 완성되는 문자열은 같다는 점을 관찰하면 위 내용을 쉽게 이해할 수 있다.

그렇다면 남은 과정은 각 비트를 대응되는 각각의 위치로 옮기는 것이다. 만약 각 문자를 옮기는 데에 대응되는 두 인덱스의 차만큼의 연산만 사용할 수 있다면 그 때의 연산의 수가 최소가 될 것임은 자명하다. 그리고 나중 문자열의 첫 문자부터 하나씩 정위치에 있게끔 연산을 차례대로 적용하면 이와 같은 횟수의 연산만을 사용해 문자열을 변환할 수 있음을 관찰할 수 있다.

더 많은 내용을 알아보고 싶다면 cp에서 자주 만나게 되는 주제인 inversion counting에 대해 조사해보자.

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

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

int N, K;
vector<int> A, B, C;
int ans = 1000000007;

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

	cin >> N >> K;
	for (int n = 0; n < N; n++) {
		int x; cin >> x;
		if (x) C.emplace_back(n);
	}
	for (int k = 0, idx = 0; k < K; k++) {
		int x; cin >> x;
		if (k & 1) {
			while (x--) {
				A.emplace_back(idx);
				idx++;
			}
		}
		else {
			while (x--) {
				B.emplace_back(idx);
				idx++;
			}
		}
	}

	if (A.size() == C.size()) {
		int val = 0, sizeA = A.size();
		for (int i = 0; i < sizeA; i++) {
			val += abs(A[i] - C[i]);
		}
		ans = min(ans, val);
	}
	if (B.size() == C.size()) {
		int val = 0, sizeB = B.size();
		for (int i = 0; i < sizeB; i++) {
			val += abs(B[i] - C[i]);
		}
		ans = min(ans, val);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 17213번 문제인 과일 서리이다.
문제는 아래 링크를 확인하자.

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

\(N\)개의 과일 각각을 적어도 하나씩은 훔쳐야하므로 이를 미리 하나씩 훔쳤다고 생각하면 구하고자하는 값은 \(N\)가지 과일 가운데 \(M-N\)개의 과일을 (중복을 허용하여) 고르는 경우의 수와 같게 된다. 이는 \(N-1\)개의 막대기와 \(M-N\)개의 과일을 나열하는 경우의 수와 같게 볼 수 있다.

파스칼의 삼각형을 이용해 위의 경우의 수를 계산하고 이를 출력해 문제를 해결하자.

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

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

ll comb[32][32];
void combinit() {
	comb[0][0] = 1;
	for (int n = 1; n < 32; n++) {
		comb[n][0] = 1;
		for (int r = 1; r <= n; r++) comb[n][r] = comb[n - 1][r - 1] + comb[n - 1][r];
	}
}

int N, M;

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

	combinit();

	cin >> N >> M;
	cout << comb[M - 1][N - 1];
}

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

이번에 볼 문제는 백준 17212번 문제인 달나라 토끼를 위한 구매대금 지불 도우미이다.
문제는 아래 링크를 확인하자.

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

각 금액 \(N>0\)을 지불하는 방법은 (1)1원 동전을 포함하거나 (2)2원 동전을 포함하거나 (3)5원 동전을 포함하거나 (4)7원 동전을 포함하는 네 경우 중 적어도 하나를 만족함을 관찰하자.

따라서 각 금액 \(N>0\)을 최소 개수의 동전으로 지불하는 방법은 (1)\(N-1\)원을 최소 개수의 동전으로 지불한 뒤 1원 동전을 추가로 지불하거나 (2)\(N-2\)원을 최소 개수의 동전으로 지불한 뒤 2원 동전을 추가로 지불하거나 (3)\(N-5\)원을 최소 개수의 동전으로 지불한 뒤 5원 동전을 추가로 지불하거나 (4)\(N-7\)원을 최소 개수의 동전으로 지불한 뒤 7원 동전을 추가로 지불하는 네 경우 중 적어도 하나를 만족함을 알 수 있다.

위 관계를 점화식으로 나타내 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;
int dp[100001];

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

	for (int i = 1; i < 100001; i++) {
		dp[i] = dp[i - 1];
		if (i > 1) dp[i] = min(dp[i], dp[i - 2]);
		if (i > 4) dp[i] = min(dp[i], dp[i - 5]);
		if (i > 6) dp[i] = min(dp[i], dp[i - 7]);
		dp[i]++;
	}

	cin >> N;
	cout << dp[N];
}

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

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

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

쌓인 소의 높이는 소의 순서에 관계없이 어떤 소가 쌓여있는지에만 영향을 받는다. 이러한 소의 조합(소 0마리로 이루어진 조합도 포함한다)은 각 소가 조합에 포함되어있는지의 여부로 결정되므로 총 \(2^N\)가지 존재한다.

가능한 모든 방법으로 소를 쌓았을 때의 높이를 하나하나 조사해 문제를 해결하자. \(2^{20}=1048576\)이므로 이와 같은 방법으로 문제를 충분히 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, K;
int ans = 1000000007;
int val, A[20];

void func(int idx) {
	if (idx == N) {
		if (val < K) return;
		ans = min(ans, val - K);
		return;
	}
	func(idx + 1);
	val += A[idx];
	func(idx + 1);
	val -= A[idx];
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	func(0);

	cout << ans;
}

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

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

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

각 꼭짓점 \(x>1\)에서 1 방향으로 거슬러 올라갈 때 만나게 되는 꼭짓점은 \(x\)를 2로 나눈 몫임을 관찰하자.

이를 이용하면 주어지는 두 꼭짓점이 같아질 때까지 더 큰 수가 부여된 꼭짓점의 수를 반으로 나누는 것을 반복하는 것으로 문제를 해결할 수 있음을 관찰할 수 있다.

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

#include <iostream>
using namespace std;

int x, y;
void solve() {
	cin >> x >> y;
	while (x != y) {
		if (x > y) x >>= 1;
		else y >>= 1;
	}

	cout << x << '0' << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}