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

 

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

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

 

17236번: Heights

각 줄에 실존하는 삼각형의 높이 값 ha, hb, hc가 각각 주어진다. ha, hb, hc는 실수이며, 0.01 ≤ ha, hb, hc ≤ 100.00이다. 삼각형의 높이는 소수점 10째자리까지 주어질 수 있다.

www.acmicpc.net

 

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

삼각형의 세 변의 길이를 \(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));
}
728x90

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

 

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

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

 

10330번: 비트 문자열 재배열하기

비트 문자열은 0, 1로만 이루어진 문자열이다. 여러분은 비트 문자열을 하나 받아서 특정한 문자열로 바꾸어야 한다. 이때, 여러분이 유일하게 할 수 있는 연산은 인접한 두 비트를 바꾸는 것이

www.acmicpc.net

 

지문에 서술되어 있듯이, 연속 코드의 형태로 주어진 문자열은 '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;
}
728x90

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

 

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

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

 

17213번: 과일 서리

민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다.

www.acmicpc.net

 

\(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];
}
728x90

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

 

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

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

 

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 

www.acmicpc.net

 

각 금액 \(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];
}
728x90

'BOJ' 카테고리의 다른 글

[BOJ 10330 // C++] 비트 문자열 재배열하기  (0) 2024.04.18
[BOJ 17213 // C++] 과일 서리  (0) 2024.04.17
[BOJ 6148 // C++] Bookshelf 2  (0) 2024.04.15
[BOJ 13116 // C++] 30번  (0) 2024.04.14
[BOJ 6511 // C++] Black and white painting  (0) 2024.04.13

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

 

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

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

 

6148번: Bookshelf 2

Here we use cows 1, 3, 4, and 5, for a total height of 3 + 3 + 5 + 6 = 17. It is not possible to obtain a total height of 16, so the answer is 1.

www.acmicpc.net

 

쌓인 소의 높이는 소의 순서에 관계없이 어떤 소가 쌓여있는지에만 영향을 받는다. 이러한 소의 조합(소 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;
}
728x90

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

 

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

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

 

13116번: 30번

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1

www.acmicpc.net

 

각 꼭짓점 \(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();
}
728x90

+ Recent posts