취미로 코딩하기

(2022-04-08 재채점 이후 수정)

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

이번에 볼 문제는 백준 2502번 문제인 떡 먹는 호랑이이다.
문제는 아래 링크를 확인하자.

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

첫 날에 준 떡의 개수를 A개, 둘째 날에 준 떡의 개수를 B개라고 하면, D번째 날에 준 떡의 개수를 피보나치 수열을 이용하여 A와 B로 나타낼 수 있다. 이를 이용하여 문제를 해결하면 된다.

A와 B가 0이 되면 안 된다는 조건을 놓치지 말고 구현하자.

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

#include <iostream>
using namespace std;

int fib[31];

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

	fib[1] = fib[2] = 1;
	for (int i = 3; i < 31; i++) fib[i] = fib[i - 1] + fib[i - 2];

	int D, K; cin >> D >> K;
	int x = fib[D - 2], y = fib[D - 1];
	int A = 1, B = 0;
	K -= x;
	while (K % y > 0) {
		A++;
		K -= x;
	}
	B = K / y;
	cout << A << '\n' << B;
}

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

이번에 볼 문제는 백준 1747번 문제인 소수&팰린드롬이다.
문제는 아래 링크를 확인하자.

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

자연수 N이 주어질 때, N 이상의 수 중 소수이면서 팰린드롬(회문)인 가장 작은 수를 구하는 문제이다.

회문을 판단하는 것은 길이가 최대 7자리이므로 간단하지만, 각 수가 소수인지 판단하는 것은 그보다 많은 연산을 필요로 하므로, 소수의 목록을 구해놓고 각 수가 회문인지를 판단하는 것이 효율적일 것이다.

100만까지의 소수목록만을 구하면 안됨에 유의하자. (입력으로 100만이 들어오면 100만보다 "큰" 소수이면서 회문인 수를 찾아야하기 때문이다.)

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

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

vector<bool> sieve(1003002);

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

	sieve[0] = sieve[1] = 1;
	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j <= 1003000; j += i) {
			sieve[j] = 1;
		}
	}

	int N; cin >> N;
	bool chk = 1;
	N--;
	while (chk) {
		N++;
		if (!sieve[N]) {
			string s = to_string(N);
			int slen = s.length();
			chk = 0;
			int L = 0, R = slen - 1;
			while (L < R) {
				if (s[L] != s[R]) chk = 1;
				L++; R--;
			}
		}
	}

	cout << N;
}

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

이번에 볼 문제는 백준 11401번 문제인 이항 계수 3이다.
문제는 아래 링크를 확인하자.

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

이항계수 하나의 소수 P로 나눈 나머지를 구하는 것은 FLT(페르마의 소정리)를 이용하여 빠르게 계산할 수 있다.

이항계수의 정의를 이용하여 (분자) * (분모의 역원) 을 이용하여 계산하자.

FLT를 이용하는 과정의 거듭제곱은 binary exponentiation을 이용하여 빠르게 계산해주자.

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

#define P 1000000007LL
#include <iostream>
using namespace std;
typedef long long ll;

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

	ll N, K; cin >> N >> K;
	ll ans = 1;
	for (ll i = 1; i <= K; i++) {
		ans *= i;
		ans %= P;
	}
	for (ll i = 1; i <= N - K; i++) {
		ans *= i;
		ans %= P;
	}
	int x = 1000000005;
	ll temp = 1;
	while (x > 0) {
		if (x & 1) {
			temp *= ans;
			temp %= P;
		}
		ans *= ans;
		ans %= P;
		x >>= 1;
	}

	ans = temp;

	for (ll i = 1; i <= N; i++) {
		ans *= i;
		ans %= P;
	}

	cout << ans;
}

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

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

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

현재 표기된 Z가 99거나 100이라면 절대 100이나 101이 될 수 없으므로 -1을 출력한다.

그렇지 않다면 이 문제는 간단한 일차부등식의 계산문제가 된다.

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

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

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

	ll X, Y; cin >> X >> Y;
	ll Z = Y * 100 / X;
	if (Z >= 99) cout << -1;
	else {
		Z++ ;
		ll A = X * Z - 100 * Y;
		ll B = 100 - Z;
		if (A % B == 0) cout << A / B;
		else cout << A / B + 1;
	}
}

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

이번에 볼 문제는 백준 10972번 문제인 다음 순열이다.
문제는 아래 링크를 확인하자.

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

algorithm 헤더의 next_permutation을 이용하여 다음 순열을 간단히 구할 수 있다.

주어진 순열이 마지막 순열이 아님을 확인하는 것을 잊지 말자.

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

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

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

	int N; cin >> N;
	vector<int> arr(N);

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

	bool chk = 1;

	for (int i = 0; i < N; i++) {
		if (arr[i] != N - i) chk = 0;
	}

	if (chk) cout << -1;

	else {
		next_permutation(arr.begin(), arr.end());
		for (auto x : arr) cout << x << ' ';
	}
}

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

이번에 볼 문제는 백준 10973번 문제인 이전 순열이다.
문제는 아래 링크를 확인하자.

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

algorithm 헤더의 prev_permutation을 이용하여 이전 순열을 간단히 구할 수 있다.

주어진 순열이 첫번째 순열이 아님을 확인하는 것을 잊지 말자.

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

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

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

	int N; cin >> N;
	vector<int> arr(N);

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

	bool chk = 1;

	for (int i = 0; i < N; i++) {
		if (arr[i] != i + 1) chk = 0;
	}

	if (chk) cout << -1;

	else {
		prev_permutation(arr.begin(), arr.end());
		for (auto x : arr) cout << x << ' ';
	}
}