취미로 코딩하기

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

이번에 볼 문제는 백준 23814번 문제인 아 저는 볶음밥이요이다.
문제는 아래 링크를 확인하자.

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

짜장면을 추가로 더 시켜 군만두를 하나 추가로 얻기 위해 더 주문해야 하는 양을 \(X\), 짬뽕에 대해 같은 값을 \(Y\)라 하자. 이 때 짜장면과 짬뽕을 각각 \(X\), \(Y\)개 초과로 주문하는 것은 항상 최선의 경우가 아님을 관찰하자. 초과한 만큼의 짜장면과 짬뽕은 각각 볶음밥으로 바꿔 주문해도 얻게 되는 군만두의 양은 변하지 않기 때문이다. 이는 짜장면과 짬뽕을 각각 \(X\)와 \(Y\)보다 적게 추가 주문할 때에도 마찬가지이다.

따라서, 짜장면과 짬뽕, 짜장면만, 짬뽕만, 둘 다 추가주문하지 않는 네 가지 경우에 대하여 군만두를 최대로 얻는 경우가 무엇인지 살펴 그 때의 볶음밥 주문량의 최댓값을 구해 문제를 해결하자.

\(K\)의 값이 충분히 크지 않아 짜장면과 짬뽕을 충분히 추가주문하지 못하는 경우도 생길 수 있음에 유의하여 구현하자.

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

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

ll D, N, M, K;
vector<pair<ll, ll>> P;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> D >> N >> M >> K;
	N %= D, M %= D;
	N = D - N, M = D - M;

	P.emplace_back(make_pair(K / D, K));
	P.emplace_back(make_pair((K - N) / D + 1, K - N));
	P.emplace_back(make_pair((K - M) / D + 1, K - M));
	P.emplace_back(make_pair((K - N - M) / D + 2, K - N - M));
	sort(P.begin(), P.end());
	while (P.back().second < 0) P.pop_back();
	cout << P.back().second;
}

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

이번에 볼 문제는 백준 16493번 문제인 최대 페이지 수이다.
문제는 아래 링크를 확인하자.

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

챕터의 수 \(M\)이 많아야 20이므로, 읽을 챕터를 고르는 경우의 수는 \(2^{20}=1048576\)가지뿐임을 관찰하자. (읽는 순서에 상관없이 읽는 데에 드는 시간과 읽은 페이지수는 변하지 않음을 확인하자.)

따라서 모든 챕터 선택의 경우를 한번씩 살피는 완전 탐색을 통해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int D, N;
int A[20], P[20];
int days, val, ans;

void func(int idx) {
    if (idx == N) {
        if (days <= D) ans = max(ans, val);
        return;
    }
    func(idx + 1);
    days += A[idx];
    val += P[idx];
    func(idx + 1);
    days -= A[idx];
    val -= P[idx];
}

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

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

    cout << ans;
}

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

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

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

주어지는 정수의 각 자리를 읽어 0, 2, 4, 6, 8 중 하나면 짝수 자릿수의 개수를, 그리고 1, 3, 5, 7, 9 중 하나면 홀수 자릿수의 개수를 하나씩 늘려나가는 방식으로 짝수 자릿수와 홀수 자릿수의 개수를 각각 구해내자.

두 값을 비교하는 것으로 문제가 요구하는 답을 구할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int cnto, cnte;

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

	cin >> N;
	while (N--) {
		char c; cin >> c;
		if ((c - '0') & 1) cnto++;
		else cnte++;
	}

	if (cnto > cnte) cout << 1;
	else if (cnto < cnte) cout << 0;
	else cout << -1;
}

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

이번에 볼 문제는 백준 31866번 문제인 손가락 게임이다.
문제는 아래 링크를 확인하자.

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

구현 편의를 위해 손가락이 1, 3, 4개 펴진 손을 나타내는 수를 하나로 먼저 통일하자.

그리고 (1) 같은 것을 내면 무승부, (2) 그 외 어느 한 사람이 "무효"를 내면 상대가 이김 둘을 먼저 처리하면 나머지는 가위바위보와 같은 상황이 됨을 관찰하자.

위와 같은 관찰을 토대로 각 게임의 승패를 판단해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int A, B;

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

    cin >> A >> B;
    if (A == 3 || A == 4) A = 1;
    if (B == 3 || B == 4) B = 1;
    if (A == B) cout << '=';
    else if (A == 1) cout << '<';
    else if (B == 1) cout << '>';
    else if (A == 0 && B == 2) cout << '>';
    else if (A == 2 && B == 5) cout << '>';
    else if (A == 5 && B == 0) cout << '>';
    else cout << '<';
}

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

이번에 볼 문제는 백준 25562번 문제인 차의 개수이다.
문제는 아래 링크를 확인하자.

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

\(N\)개의 수의 차의 가짓수의 최댓값은 \(N(N-1)/2\) 이하임은 자명하다. 이는 \(N\)개의 수 중 서로 다른 두 수를 고르는 경우의 수와 같다. 한편 \(N\)개의 수를 \(2^k\) (단, \(k\)는 0 이상 \(N\) 미만의 정수)와 같이 고르면 어떤 두 수를 골라도 차가 같게 나오는 경우가 없음을 확인할 수 있다. (이해가 잘 안 된다면, 두 수의 차를 이진수로 나타내 차가 어떠한 형태로 나타나는지를 관찰해보자.) 따라서 \(2^k\) (단, \(k\)는 0 이상 \(N\) 미만의 정수)와 같이 \(N\)개의 수를 고르는 것은 차의 가짓수를 최대(\(N(N-1)/2\)개)로 하는 방법이 됨을 알 수 있다.

\(N\)개의 수의 차의 가짓수의 최솟값은 \(N-1\) 이상임은 자명하다. \(N\)개의 수 중 가장 큰 수와 나머지 수와의 차의 값은 서로 다르기 때문이다. 한편 \(N\)개의 수를 1 이상 \(N\) 이하와 같이 고르면 가능한 차는 각각 1 이상 \(N-1\) 이하의 총 \(N-1\)가지가 됨을 알 수 있다. 따라서 1부터 \(N\)까지의 수를 고르는 것은 차의 가짓수를 최소(\(N-1\)개)로 하는 방법이 됨을 알 수 있다.

위 관찰을 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	cout << N * (N - 1) / 2 << '\n';
	for (int i = 0; i < N; i++) cout << (1 << i) << ' ';
	cout << '\n' << N - 1 << '\n';
	for (int i = 1; i <= N; i++) cout << i << ' ';
}

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

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

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

주어진 이산함수의 립시츠 상수(Lipschitz Constant)를 구하는 문제이다. 립시츠 상수는 함수 위의 서로 다른 두 점을 이어 얻을 수 있는 직선의 기울기의 절댓값의 상계(upper bound)를 의미한다.

서로 다른 세 \(x\)좌표 \(x_1\), \(x_2\), \(x_3\)에 대하여 \(x_1\)과 \(x_3\)을 이어 얻을 수 있는 직선의 기울기의 절댓값은 항상 \(x_1\), \(x_2\)를 이어 얻을 수 있는 직선의 기울기의 절댓값, 그리고 \(x_2\), \(x_3\)를 이어 얻을 수 있는 직선의 기울기의 절댓값 둘 중 하나보다 작거나 같은 값을 가질 수밖에 없음을 관찰하자. 증명은 양의 실수 \(a\), \(c\)와 실수 \(b\), \(d\)에 대하여 \(\frac{b}{a}<\frac{d}{c}\)이면 \( \frac{b}{a}  < \frac{b+d}{a+c} < \frac{d}{c} \)이 성립함을 이용해 간단하게 할 수 있다.

따라서 주어진 문제에서 립시츠 상수는 각 \(x\)값들을 오름차순으로 정렬했을 때 서로 이웃한 차례의 \(x\)값을 갖는 점들끼리의 기울기만을 확인하는 것으로 구할 수 있다. 이를 구현해 문제를 해결하자.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;

int N;
vector<pair<int, ld>> vec;
ld ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; ld y; cin >> x >> y;
		vec.emplace_back(make_pair(x, y));
	}

	sort(vec.begin(), vec.end());

	for (int i = 0; i + 1 < N; i++) {
		ans = max(ans, abs((vec[i + 1].second - vec[i].second) / (vec[i + 1].first - vec[i].first)));
	}

	cout << fixed;
	cout.precision(10);
	cout << ans;
}