취미로 코딩하기

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

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

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

동전 모음이 하나인 경우 그 모음을 고르면 된다. 동전 모음이 둘 이상이라고 가정해보자.

어떤 두 위치를 선택해 동전을 가져갈 때, 이 두 위치 사이에 셋 이상의 동전 모음이 있다면 둘 사이의 동전을 적어도 하나는 더 골라야 함을 관찰하자. 적어도 하나 이상의 동전 모음을 더 고를 수 있는데 안 고르면 그 경우를 최적으로 볼 수 없기때문이다. 비슷한 이유로 첫 두 동전 모음 중 적어도 하나의 동전 모음을 항상 골라야 하며, 마지막 두 동전 모음 중 적어도 하나의 동전 모음을 항상 골라야 함을 관찰하자.

따라서 두 칸 이전의 칸을 골랐었는지 여부와 세 칸 이전의 칸을 골랐었는지 여부를 기준으로 점화식을 세워 dp로 문제를 해결할 수 있다.

항상 첫 칸의 동전이나 마지막 칸의 동전을 골라야 할 필요는 없음에 유의하자.

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

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

int N;
string s;
int A[20];
int dp[20];

void solve() {
	getline(cin, s);
	s += ' ';
	N = 0;
	int val = 0;
	for (auto &l : s) {
		if (l == ' ') {
			A[N] = val;
			N++;
			val = 0;
		}
		else val = val * 10 + (l - '0');
	}

	if (N == 1) {
		cout << A[0] << '\n';
		return;
	}
	int ans = max(A[0], A[1]);
	dp[0] = A[0], dp[1] = A[1];
	for (int i = 2; i < N; i++) {
		if (i > 2) dp[i] = max(dp[i - 2], dp[i - 3]) + A[i];
		else dp[i] = dp[i - 2] + A[i];
		ans = max(ans, dp[i]);
	}
	cout << ans << '\n';
}

int T;

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

	cin >> T;
	getline(cin, s);
	while (T--) solve();
}

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

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

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

\(n\)이 500 이하로 충분히 작은 점을 눈여겨보자. 이 정도의 제한이면 각각의 별에 대하여 그 별과 가장 가까운 별(들)을 다른 별들을 한번씩 확인하는 것으로 충분히 구할 수 있다.

각 별에 대하여 가장 가까운 별들의 모임을 구하고, "한 별이 다른 별의 가장 가까운 별 중 하나"의 관계를 만족하는 두 별을 하나의 별자리로 합쳐 문제를 해결하자. 이 과정은 disjoint set 자료구조를 이용하면 쉽게 구현 가능하다.

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

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

int N;
int X[500], Y[500];
int uf[500];
int findf(int x) {
    if (x == uf[x]) return x;
    return uf[x] = findf(uf[x]);
}
void solve() {
    for (int i = 0; i < N; i++) uf[i] = i;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
    }
    for (int i = 0; i < N; i++) {
        int mn = 1000000007; vector<int> vec;
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            int dx = X[i] - X[j], dy = Y[i] - Y[j];
            int val = dx * dx + dy * dy;
            if (val < mn) {
                vec.clear();
                mn = val, vec.emplace_back(j); 
            }
            else if (val == mn) vec.emplace_back(j);
        }
        for (auto &x:vec) {
            int y = findf(i), z = findf(x);
            uf[z] = y;
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (i == findf(i)) ans++;
    }

    cout << ans << " constellations.\n";
}

int T;

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

    cin >> N;
    while (N) {
        T++;
        cout << "Sky " << T << " contains ";
        solve();
        cin >> N;
    }
}

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

이번에 볼 문제는 백준 3933번 문제인 라그랑주의 네 제곱수 정리이다.
문제는 아래 링크를 확인하자.

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

문제로 주어지는 수가 2의 15승, 즉 32768 이하이고, 각 수의 합을 구성할 수 있는 수는 32768 이하의 제곱수 181가지뿐임을 확인하자.

이를 이용하면 이 문제를 0-1 배낭문제(0-1 knapsack)와 같은 형태로 모델링해 해결할 수 있음을 어렵지 않게 관찰할 수 있다.

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

#include <iostream>
using namespace std;

int dp[5][32768];
int N;

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

    dp[0][0] = 1;
    for (int i = 1; i * i < 32768; i++) {
        for (int k = 1; k < 5; k++) {
            for (int ii = i * i; ii < 32768; ii++) {
                dp[k][ii] += dp[k - 1][ii - i * i];
            }
        }
    }

    cin >> N;
    while (N) {
        cout << dp[1][N] + dp[2][N] + dp[3][N] + dp[4][N] << '\n';
        cin >> N;
    }
}

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

이번에 볼 문제는 백준 30510번 문제인 토마에 함수이다.
문제는 아래 링크를 확인하자.

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

이 문제는 Thomae's Function(토메 함수)을 소재로 한 문제이다. Thomae's Function은 모든 유리수점에서 불연속이고 무리수점에서 연속인 함수로, 자세한 설명은 이 문제의 해결에 필요한 범주를 넘어서므로 생략한다.

\(f\)의 함숫값은 (0을 제외하면) 항상 단위분수의 형태로 나타남을 관찰하자. 따라서 조건을 만족시키는 실수 \(x\)의 함숫값으로 나타날 수 있는 주어진 수보다 큰 단위분수 \(\frac{1}{N}\)을 이분탐색으로 먼저 구한다면, 조건을 만족시키는 \(x\)들(0 제외)은 분모가 \(N\) 이하인 기약분수(\(\frac{1}{1}\) 포함)의 형태로 나타남을 관찰하자.

이와 같은 \(x\)의 개수는 Euler Totient Function을 이용해 빠르게 계산할 수 있다. Euler Totient의 함숫값은 Sieve of Eratosthenes(에라토스테네스의 체)와 같은 방식으로 빠르게 전처리할 수 있음을 이용해 문제를 해결하자.

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

//30510: Euler Phi
#include <iostream>
using namespace std;
typedef long long ll;

ll P, Q, L = 1, R = 100000;
bool sieve[100001];
ll eulerphi[100001];

void init() {
    sieve[0] = sieve[1] = 1;
    for (int i = 2; i * i < 100001; i++) {
        if (sieve[i]) continue;
        for (int j = i * i; j < 100001; j += i) sieve[j] = 1;
    }
    for (int i = 1; i < 100001; i++) eulerphi[i] = i;
    for (int i = 1; i < 100001; i++) {
        if (sieve[i]) continue;
        for (int j = i; j < 100001; j += i) {
            eulerphi[j] /= i;
            eulerphi[j] *= i - 1;
        }
    }
}

ll ans;

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

    cin >> P >> Q;
    while (L < R) {
        ll mid = (L + R) / 2 + 1;
        if (Q >= P * mid) L = mid;
        else R = mid - 1;
    }

    init();
    for (int i = 1; i <= L; i++) ans += eulerphi[i];
    cout << ans + 1;
}

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

이번에 볼 문제는 백준 30509번 문제인 그래서 나는 코딩을 그만두었다이다.
문제는 아래 링크를 확인하자.

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

세종이가 \(K\)회 코딩 대결을 할 수 있다면 \(K\) 이하회의 코딩 대결은 항상 할 수 있고, \(K'\)회 코딩 대결을 할 수 없다면 \(K'\)회 코딩 대결은 항상 할 수 없음을 관찰하자. 따라서 세종이가 \(K\)회의 코딩 대결을 할 수 있는지에 대한 답을 구하는 결정문제를 해결할 수 있다면 전체 문제의 답은 이분탐색을 통해 구할 수 있음을 알 수 있다. 이 결정문제를 해결하는 데에 초점을 맞춰보자.

먼저, 전체 일정에서 휴식을 일정의 시작에 몰아서 하는 경우만을 살펴도 충분함을 관찰하자. \(K\)회의 코딩 대결이 어떠한 일정으로 가능하다면, 그 일정에서 휴식일을 일정의 시작으로 모두 앞당겨 얻을 수 있는 새로운 일정으로도 \(K\)회의 코딩 대결이 가능하기 때문이다.

그 다음으로, 이길 수 있는 상대와 그렇지 않은 상대와의 대결 중 이길 수 있는 상대와 먼저 대결을 하는 것이 항상 이득이다. 상대와의 대결 순서 중 \(K\)회의 대결을 소화할 수 있는 일정이 존재한다면 그 일정에서 "이기는" 대결의 일정을 (이기는 대결끼리의 순서는 그대로 유지하면서) 앞당겨도 대결이 가능하기 때문이다. 따라서, 이길 수 있는 상대가 남지 않을 때까지 계속 이기는 선택을 반복하는 것이 최선의 전략이 됨을 알 수 있다.

한편, 더 이상 이길 수 있는 상대가 남지 않았을 경우 대결 후 멘탈 수치의 감소량이 적은 상대부터 그리디하게 대결하는 것으로 대결 횟수를 최대화할 수 있음은 어렵지 않게 관찰할 수 있다.

위의 내용을 종합해 문제를 해결하는 코드를 작성하자.

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

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

ll N, XX, YY, LOSE, REST;
vector<pair<ll, ll>> vec;
ll L, R;

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

    cin >> N >> LOSE >> REST >> XX >> YY;
    vec.reserve(N);
    for (int i = 0; i < N; i++) {
        int x, y; cin >> x >> y;
        vec.emplace_back(make_pair(x + y, x));
    }

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

    L = 0, R = N;
    while (L < R) {
        ll mid = (L + R) / 2 + 1;
        ll Y = YY + (N - mid) * REST;
        int i = 0;
        for (; i < mid; i++) {
            if (XX + Y > vec[i].first) {
                if (XX < vec[i].second) Y += vec[i].second - XX;
            }
            else if (XX + Y == vec[i].first) continue;
            else break;
        }
        priority_queue<int> pq;
        for (int ii = i; ii < N; ii++) pq.push(vec[ii].second);
        for (; i < mid; i++) {
            Y -= LOSE;
            if (pq.top() < XX) Y -= XX - pq.top();
            pq.pop();
        }
        if (Y > 0) L = mid;
        else R = mid - 1;
    }

    cout << L;
}

24-08-01: 코드의 잘못 구현된 부분을 수정하였다.

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

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

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

체스판 위에서 나이트와 같은 말의 움직임으로 주어진 두 칸 사이를 이동하기 위한 최소 움직임의 횟수를 구하는 문제이다.

각 칸을 노드로, 각 칸에서 움직일 수 있는 다음 (최대) 8가지 움직임을 에지로 하는 그래프로 문제 상황을 모델링하면 주어진 문제는 두 칸을 나타내는 노드 사이의 최단거리와 같음을 알 수 있다. 이 때 모든 에지의 가중치는 같으므로 이 문제는 BFS 등의 알고리즘을 이용해 간단하게 해결할 수 있다.

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

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

int sR, sC, eR, eC;
int dist[9][9];
queue<pair<int, int>> que;
int dr[8] = { 2,1,-1,-2,-2,-1,1,2 };
int dc[8] = { 1,2,2,1,-1,-2,-2,-1 };
void bfs() {
	dist[sR][sC] = 1;
	que.push(make_pair(sR, sC));
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 1 || rr > 8 || cc < 1 || cc > 8 || dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> sR >> sC >> eR >> eC;
	bfs();

	cout << dist[eR][eC] - 1;
}